TY - GEN

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

AU - Koutis, Ioannis

AU - Miller, Gary L.

N1 - Funding Information:
This work was supported in part by the National Science Foundation under grants CCR-9902091, CCR-9706572, ACI 0086093, CCR-0085982 and CCR-0122581
Publisher Copyright:
Copyright © 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79959646222&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959646222&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:79959646222

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1002

EP - 1011

BT - Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007

PB - Association for Computing Machinery

T2 - 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007

Y2 - 7 January 2007 through 9 January 2007

ER -