Sparsified Cholesky Solvers for SDD linear systems

2015/06/26 by Lee, Yin Tat, Peng, Richard, Spielman, Daniel A.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1506.08204

Abstract

We show that Laplacian and symmetric diagonally dominant (SDD) matrices can be well approximated by linear-sized sparse Cholesky factorizations. We show that these matrices have constant-factor approximations of the form L L^T, where L is a lower-triangular matrix with a number of nonzero entries linear in its dimension. Furthermore linear systems in L and L^T can be solved in O (n) work and O(lognlog²logn) depth, where n is the dimension of the matrix. We present nearly linear time algorithms that construct solvers that are almost this efficient. In doing so, we give the first nearly-linear work routine for constructing spectral vertex sparsifiers---that is, spectral approximations of Schur complements of Laplacian matrices.

Related

• Faster spectral sparsification and numerical algorithms for SDD matrices
• Algorithm 887
• Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
• Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O (m^1.31)
• A nearly-mlogn time solver for SDD linear systems