  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.
