Solving linear systems through nested dissection

Noga Alon, Raphael Yuster

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

8 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
Pages225-234
Number of pages10
DOIs
StatePublished - 2010
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, NV, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

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

Other

Other2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
CountryUnited States
CityLas Vegas, NV
Period10/23/1010/26/10

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

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

    Alon, N., & Yuster, R. (2010). Solving linear systems through nested dissection. In Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 (pp. 225-234). [5671172] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2010.28