## 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(n^{1/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 log^{2} 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 |

Publisher | Association for Computing Machinery |

Pages | 1002-1011 |

Number of pages | 10 |

ISBN (Electronic) | 9780898716245 |

State | Published - 2007 |

Externally published | Yes |

Event | 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States Duration: Jan 7 2007 → Jan 9 2007 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 07-09-January-2007 |

### Other

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

Country/Territory | United States |

City | New Orleans |

Period | 1/7/07 → 1/9/07 |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint

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