Sparse LDL, LU, and inverse butterfly factorization via tree decomposition
This work provides the first rigorous complexity bounds for symmetric triangular factorization in terms of treewidth, offering a theoretical foundation for sparse direct solvers.
The paper presents new algorithms for symmetric LDL and LU factorization that achieve near-optimal complexity for both dense and sparse matrices, with the sparse case depending on treewidth. For dense matrices, the LDL algorithm runs in O(n^ω) time, and for sparse matrices with treewidth τ, it runs in O(n τ^{ω-1}) time. The authors also show that the inverse of a full-rank bounded-treewidth matrix has an exact butterfly factorization with rank O(τ).
While linear systems over general fields can be solved in matrix-multiplication time, the complexity of symmetric triangular factorization has received relatively little formal study. We give dense and sparse LDL algorithms for symmetric matrices over an arbitrary field. Both algorithms leverage pivoted (rank-revealing) LU on off-diagonal blocks of a saddle-point form of a general symmetric matrix. For an $n\times n$ matrix, this yields an $O(n^ω)$ dense LDL algorithm, where $n\times n$ matrix multiplication is assumed to cost $O(n^ω)$ with $ω>2$. For sparse matrices whose graph has treewidth $τ$, we provide an implicit LDL in $O(nτ^{ω-1})$ time, and an explicit LDL whenever the rank deficiency is $O(τ)$. We give analogous results for sparse LU via a standard off-diagonal embedding. We also obtain bounds on work, storage, and parallel-depth in terms of the dense $τ\timesτ$ kernels executed at each bag in a tree decomposition. Finally, in the full-rank bounded-treewidth setting, we prove that $A^{-1}$ has complementary low-rank structure and admits an exact butterfly factorization with rank $O(τ)$.