Structured Semidefinite Programming for Recovering Structured Preconditioners
This work addresses the computational bottleneck of preconditioning and linear system solving in numerical linear algebra, offering significant speedups for practitioners in fields like scientific computing and machine learning, though it is incremental as it builds on existing semidefinite programming methods.
The paper tackles the problem of finding efficient preconditioners for solving linear systems by developing a structured semidefinite programming framework, resulting in improved runtimes such as computing an ε-optimal diagonal preconditioner in time O~(nnz(K) · poly(κ*, ε⁻¹)) and solving linear systems in O~(d²) time for specific matrices, compared to previous state-of-the-art runtimes of Ω(d³·⁵) and Ω(d^ω).
We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental preconditioning and linear system solving problems including the following. We give an algorithm which, given positive definite $\mathbf{K} \in \mathbb{R}^{d \times d}$ with $\mathrm{nnz}(\mathbf{K})$ nonzero entries, computes an $ε$-optimal diagonal preconditioner in time $\widetilde{O}(\mathrm{nnz}(\mathbf{K}) \cdot \mathrm{poly}(κ^\star,ε^{-1}))$, where $κ^\star$ is the optimal condition number of the rescaled matrix. We give an algorithm which, given $\mathbf{M} \in \mathbb{R}^{d \times d}$ that is either the pseudoinverse of a graph Laplacian matrix or a constant spectral approximation of one, solves linear systems in $\mathbf{M}$ in $\widetilde{O}(d^2)$ time. Our diagonal preconditioning results improve state-of-the-art runtimes of $Ω(d^{3.5})$ attained by general-purpose semidefinite programming, and our solvers improve state-of-the-art runtimes of $Ω(d^ω)$ where $ω> 2.3$ is the current matrix multiplication constant. We attain our results via new algorithms for a class of semidefinite programs (SDPs) we call matrix-dictionary approximation SDPs, which we leverage to solve an associated problem we call matrix-dictionary recovery.