We introduce the sparsified Cholesky and sparsified multigrid
algorithms for solving systems of linear equations. These algorithms
accelerate Gaussian elimination by sparsifying the nonzero matrix
entries created by the elimination process.

We use these new algorithms to derive the first nearly linear time
algorithms for solving systems of equations in connection Laplacians,
a generalization of Laplacian matrices that arise in many problems in
image and signal processing.

We also prove that every connection Laplacian has a linear sized
approximate inverse. This is an LU factorization with a linear number
of nonzero entries that is a strong approximation of the original
matrix. Using such a factorization one can solve systems of equations
in a connection Laplacian in linear time. Such a factorization was
unknown even for ordinary graph Laplacians.

Joint work with Rasmus Kyng, Yin Tat Lee, Sushant Sachdeva, and Daniel
Spielman. Manuscript at http://arxiv.org/abs/1512.01892.