A linear work, O(n1/6) time, parallel algorithm for solving planar Laplacians

Ioannis Koutis, Gary L. Miller

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

29 Scopus citations

Abstract

We present a linear work parallel iterative algorithm for solving linear systems involving Laplacians of planar graphs. In particular, if Ax = b, where A is the Laplacian of any planar graph with n nodes, the algorithm produces a vector x such that ||x - x||A ≤ ∈, in O(n1/6+c log(1/∈)) parallel time, doing O(n log(1/∈)) work, where c is any positive constant. One of the key ingredients of the solver, is an O(nk log2 k) work, O(k log n) time, parallel algorithm for decomposing any embedded planar graph into components of size O(k) that are delimited by O(n/√k) boundary edges. The result also applies to symmetric diagonally dominant matrices of planar structure.

Original languageEnglish (US)
Title of host publicationProceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PublisherAssociation for Computing Machinery
Pages1002-1011
Number of pages10
ISBN (Electronic)9780898716245
StatePublished - 2007
Externally publishedYes
Event18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States
Duration: Jan 7 2007Jan 9 2007

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume07-09-January-2007

Other

Other18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Country/TerritoryUnited States
CityNew Orleans
Period1/7/071/9/07

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'A linear work, O(n<sup>1/6</sup>) time, parallel algorithm for solving planar Laplacians'. Together they form a unique fingerprint.

Cite this