  We propose a new algorithm for the fast solution of large, sparse, symmetric
positive-definite linear systems, spaND -- sparsified Nested Dissection. It is
based on nested dissection, sparsification and low-rank compression. After
eliminating all interiors at a given level of the elimination tree, the
algorithm sparsifies all separators corresponding to the interiors. This
operation reduces the size of the separators by eliminating some degrees of
freedom but without introducing any fill-in. This is done at the expense of a
small and controllable approximation error. The result is an approximate
factorization that can be used as an efficient preconditioner. We then perform
several numerical experiments to evaluate this algorithm. We demonstrate that a
version using orthogonal factorization and block-diagonal scaling takes fewer
CG iterations to converge than previous similar algorithms on various kinds of
problems. Furthermore, this algorithm is provably guaranteed to never break
down and the matrix stays symmetric positive-definite throughout the process.
We evaluate the algorithm on some large problems and show it exhibits
near-linear scaling. The factorization time is roughly O(N) and the number of
iterations grows slowly with N.
