The generalized nested dissection method, developed by Lipton et al. , is a seminal method for solving a linear system Ax = b where A is a symmetric positive definite matrix. The method runs extremely fast whenever Ais a well-separablematrix (such as matrices whose underlying support is planar or avoids a fixed minor). In this work, we extend the nested dissection method to apply to any nonsingular well-separable matrix over any field. 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.
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence