Structured Semidefinite Programming for Recovering Structured Preconditioners - Jambulapati, Arun; Li, Jerry; Musco, Christopher; Shiragur, Kirankumar; Sidford, Aaron; Tian, Kevin (NeurIPS 2023, 2023)
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:Diagonal preconditioning. We give an algorithm which, given positive definite [K] [R]^[d × d] with [nnz]([K]) nonzero entries, computes an ε-optimal diagonal preconditioner in time [O]([nnz]([K]) · [poly](κ^,ε^[-1])), where κ^ is the optimal condition number of the rescaled matrix.Structured linear systems. We give an algorithm which, given [M] [R]^[d × d] that is either the pseudo-inverse of a graph Laplacian matrix or a constant spectral approximation of one, solves linear systems in [M] in [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.