Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth
Martin Fürer, Carlos Hoppen, Vilmar Trevisan · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2020
Let M = (m_{ij}) be a symmetric matrix of order n and let G be the graph with vertex set {1,…,n} such that distinct vertices i and j are adjacent if and only if m_{ij} ≠ 0. We introduce a dynamic programming algorithm that finds a diagonal matrix that is congruent to M. If G is given with a tree decomposition 𝒯 of width k, then this can be done in time O(k|𝒯| + k² n), where |𝒯| denotes the number of nodes in 𝒯.