### Matrix sparsification and nested dissection over arbitrary fieldsMatrix sparsification and nested dissection over arbitrary fields

Access Restriction
Subscribed

 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

Source: ACM Digital Library