2026-07-25T12:38:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24585 2025-09-23T11:51:19Z ddc:004 open_access

Fast Gaussian Elimination for Low Treewidth Matrices Fürer, Martin Hoppen, Carlos Trevisan, Vilmar Gaussian elimination FPT algorithms treewidth 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Fürer and Carlos Hoppen and Vilmar Trevisan 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi: https://drops.dagstuhl.de/entities/document eng https://creativecommons.org/licenses/by/4.0/legalcode