Solving linear systems through nested dissection

Noga Alon, Raphael Yuster

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

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 nonsingular well-separable matrix over any field. The running times we obtain essentially match those of the nested dissection method.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
PublisherIEEE Computer Society
Pages225-234
Number of pages10
ISBN (Print)9780769542447
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Country/TerritoryUnited States
CityLas Vegas
Period10/23/1010/26/10

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • Gaussian elimination
  • Linear system
  • Nested dissection

Fingerprint

Dive into the research topics of 'Solving linear systems through nested dissection'. Together they form a unique fingerprint.

Cite this