Matrix sparsification and nested dissection over arbitrary fields

Noga Mordechai Alon, Raphael Yuster

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

The generalized nested dissection method, developed by Lipton et al. [1979], 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.

Original languageEnglish (US)
Article number25
JournalJournal of the ACM
Volume60
Issue number4
DOIs
StatePublished - Aug 1 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Matrix sparsification and nested dissection over arbitrary fields'. Together they form a unique fingerprint.

Cite this