Matrix sparsification and nested dissection over arbitrary fields
Noga Alon, Raphael Yuster · Journal of the ACM · 2013
The generalized nested dissection method, developed by Lipton et al. [1979], is a seminal method for solving a linear systemAx=bwhereAis a symmetric positive definite matrix. The method runs extremely fast wheneverAis a well-separable matrix (such as matrices whose underlying support is planar or avoids a fixed minor). In this work, we extend the nested dissection method to apply toanynonsingular well-separable matrix overanyfield. The running times we obtain essentially match those of the nested dissection method. An important tool is a novel method for matrix sparsification that preserves determinants and minors, and that guarantees that constant powers of the sparsified matrix remain sparse.