2025/04/28 by Edgar Solomonik, Solomonik, Edgar · 1 citation
Computer Science · #15-02 #65Yxx #68Qxx #Cryptography and Residue Arithmetic #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2504.20305
openalex publication_date 2025/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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× n matrix, this yields an O(nω) dense LDL algorithm, where n× 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 τ×τ 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(τ).