DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2025.116

Fast Gaussian Elimination for Low Treewidth Matrices

Authors: Martin Fürer, Carlos Hoppen, and Vilmar Trevisan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

Let A = (a_{ij}) be an m× n matrix whose elements lie in an arbitrary field 𝔽, and let G be the bipartite graph with vertex set {v_1,…,v_m} ∪ {w_1,…,w_n} such that vertices v_i and w_j are adjacent if and only if a_{ij} ≠ 0. We introduce an algorithm that finds an m× n matrix U in row echelon form and a permutation matrix Q of order n, such that AQ is row equivalent to U. If a tree decomposition 𝒯 of G of width k and size O(k(m+n)) is part of the input, then Q and the columns of U that contain a pivot can be computed in time O(k²(m+n)). Among other things, this allows us to compute the rank and the determinant of A in time O(k²(m+n)). It also allows us to decide in time O(k²(m+n)) whether the linear system Ax = b has a solution and to compute a solution of the linear system in case it exists.

Cite as

Martin Fürer, Carlos Hoppen, and Vilmar Trevisan. Fast Gaussian Elimination for Low Treewidth Matrices. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 116:1-116:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{furer_et_al:LIPIcs.ESA.2025.116,
  author =	{F\"{u}rer, Martin and Hoppen, Carlos and Trevisan, Vilmar},
  title =	{{Fast Gaussian Elimination for Low Treewidth Matrices}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{116:1--116:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.116},
  URN =		{urn:nbn:de:0030-drops-245855},
  doi =		{10.4230/LIPIcs.ESA.2025.116},
  annote =	{Keywords: Gaussian elimination, FPT algorithms, treewidth}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.52

Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth

Authors: Martin Fürer, Carlos Hoppen, and Vilmar Trevisan

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

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 𝒯.

Cite as

Martin Fürer, Carlos Hoppen, and Vilmar Trevisan. Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 52:1-52:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{furer_et_al:LIPIcs.ICALP.2020.52,
  author =	{F\"{u}rer, Martin and Hoppen, Carlos and Trevisan, Vilmar},
  title =	{{Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{52:1--52:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.52},
  URN =		{urn:nbn:de:0030-drops-124590},
  doi =		{10.4230/LIPIcs.ICALP.2020.52},
  annote =	{Keywords: Treewidth, Diagonalization, Eigenvalues}
}

Search Results

Documents authored by Trevisan, Vilmar

Fast Gaussian Elimination for Low Treewidth Matrices

Abstract

Cite as

Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth

Abstract

Cite as

Thanks for your feedback!

Could not send message