Access Restriction

Author Alon, Noga ♦ Yuster, Raphael
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2013
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Gaussian elimination ♦ Linear system ♦ Matrix sparsification ♦ Nested dissection
Abstract The generalized nested dissection method, developed by Lipton et al. [1979], is a seminal method for solving a linear system $\textit{Ax}=\textit{b}$ where $\textit{A}$ is a symmetric positive definite matrix. The method runs extremely fast whenever $\textit{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 $\textit{any}$ nonsingular well-separable matrix over $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2013-09-04
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 60
Issue Number 4
Page Count 18
Starting Page 1
Ending Page 18

Open content in new tab

   Open content in new tab
Source: ACM Digital Library