Fast Gaussian Elimination for Low Treewidth Matrices

Let A = (a_ij) be an m × n matrix whose elements lie in an arbitrary field F, and let G be the bipartite graph with vertex set {v1, . . ., vm}∪{w1, . . ., wn} such that vertices vi and wj are adjacent if and only if aij ≠ 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 T 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.