A linear work, O(n1/6) time, parallel algorithm for solving planar Laplacians
Ioannis Koutis, Gary Lee Miller · 2007
We present a linear work parallel iterative algorithm for solving linear systems involving Laplacians of pla-nar graphs. In particular, if Ax = b, where A is the Laplacian of any planar graph with n nodes, the al-gorithm 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. 1