Solving Linear Systems through Nested Dissection

The generalized nested dissection method, developed by Lipton, Rose, and Tarjan, 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 A is 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 to any non-singular well-separable matrix over any field. The running times we obtain essentially match those of the nested dissection method.

Authors

• Noga Alon
• Raphael Yuster

Keywords

• Transmission line matrix methods
• Symmetric matrices
• Particle separators
• Sparse matrices
• Linear systems
• Complexity theory
• Gallium
• Linear System
• Nested Dissection
• Running Time
• Symmetric Matrix
• Positive Definite Matrix
• Singular Matrix
• Symmetric Positive Definite Matrix
• Diagonal Matrix
• Unique Solution
• Matrix Multiplication
• Extensive Field
• System Of Linear Equations
• Arithmetic Operations
• Elimination Process
• Triangular Matrix
• Nonzero Entries
• Linear Algebra
• Recursive Algorithm
• Finite Field
• Largest Element
• Planar Graphs
• Gaussian Elimination
• Entry In Row
• Underlying Graph
• Sparse Algorithm
• Family Of Graphs
• Subset Of Indices