More Web Proxy on the site http://driver.im/

Article

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

Authors:

Ioannis Koutis,

Gary L. MillerAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 1002 - 1011

Published: 07 January 2007 Publication History

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+clog(1/ε)) parallel time, doing O(nlog(1/ε)) work, where c is any positive constant. One of the key ingredients of the solver, is an O(nklog²k) work, O(klogn) 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.

References

[1]

Erik G. Boman, Bruce Hendrickson, and Stephen A. Vavasis. Solving elliptic finite element systems in near-linear time with support preconditioners. CoRR, cs. NA/0407022, 2004.

[2]

William L. Briggs, Van Emden Henson, and Steve F. McCormick. A multigrid tutorial: second edition. Society for Industrial and Applied Mathematics, 2000.

Digital Library

[3]

F. R. K. Chung. Spectral graph theory. Regional Conference Series in Mathematics, American Mathematical Society, 92, 1997.

[4]

James W. Demmel. Applied Numerical Linear Algebra. SIAM, 1997.

Digital Library

[5]

Peter G. Doyle and J. Laurie Snell. Random Walks and Electrical Networks. Mathematical Association of America, 1984.

[6]

Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-stretch spanning trees. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 494--503, 2005.

Digital Library

[7]

Francois Fouss, Alain Pirotte, and Marco Saerens. A novel way of computing similarities between nodes of a graph, with application to collaborative recommendation. In ACM International Conference on Web Intelligence, pages 550--556, 2005.

Digital Library

[8]

Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16(6):1004--1022, 1987.

Digital Library

[9]

Hillel Gazit and Gary L. Miller. A parallel algorithm for finding a separator in planar graphs. In 28th Annual Symposium on Foundations of Computer Science, pages 238--248, Los Angeles, October 1987. IEEE.

[10]

Michael T. Goodrich. Planar separators and parallel polygon triangulation. J. Comput. Syst. Sci., 51(3):374--389, 1995.

Digital Library

[11]

Leo Grady. Random walks for image segmentation. EEE Trans. on Pattern Analysis and Machine Intelligence, to appear, 2006.

Digital Library

[12]

Keith Gremban. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University, Pittsburgh, October 1996.

[13]

John E. Hopcroft and Robert Endre Tarjan. Efficient planarity testing. J. ACM, 21(4):549--568, 1974.

Digital Library

[14]

Marcos A. Kiwi, Daniel A. Spielman, and Shang-Hua Teng. Min-max-boundary domain decomposition. Theor. Comput. Sci., 261(2):253--266, 2001.

Digital Library

[15]

Philip N. Klein. On Gazit and Miller's parallel algorithm for planar separators: Achieving greater efficiency through random sampling. In Procedings of SPAA, pages 43--49, 1993.

Digital Library

[16]

Philip N. Klein and John H. Reif. An efficient parallel algorithm for planarity. J. Comput. Syst. Sci., 37(2):190--246, 1988.

Digital Library

[17]

R. J. Lipton and R. E. Tarjan. A planar separator theorem. SIAM J. of Applied Math., 36(2):177--189, April 1979.

[18]

Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15(4):1036--1053, 1986.

Digital Library

[19]

Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, and Shan Leung Maverick Woo. Finding effective support-tree preconditioners. In Procideengs of SPAA, pages 176--185, 2005.

Digital Library

[20]

Gary L. Miller. Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences, 32(3):265--279, June 1986. invited publication.

Digital Library

[21]

Gary L. Miller and Peter C. Richter. Lower bounds for graph embeddings and combinatorial preconditioners. In Procedings of SPAA, pages 112--119, 2004.

Digital Library

[22]

A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm, 2001.

[23]

Victor Y. Pan and John H. Reif. Fast and efficient parallel solution of sparse linear systems. SIAM J. Comput., 22(6):1227--1250, 1993.

Digital Library

[24]

Vijaya Ramachandran and John H. Reif. Planarity testing in parallel. J. Comput. Syst. Sci., 49(3):517--561, 1994.

Digital Library

[25]

Margaret Reid-Miller, Gary L. Miller, and Frances-mary Modugno. List ranking and parallel tree contraction. In Synthesis of Parallel Algorithms, pages 115--194. Morgan Kaufmann, 1993.

[26]

R. E. Tarjan R. J. Lipton and D. Rose. Generalized nested dissection. SIAM Journal of Numerical Analysis, 16:346--358, 1979.

[27]

Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th STOC, pages 81--90, June 2004.

Digital Library

[28]

David Tolliver and Gary L. Miller. Graph partitioning by spectral rounding: Applications in image segmentation and clustering. In CVPR, 2006.

Digital Library

[29]

P. M. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript, October 1991.

Cited By

Dell'Acqua PFrangioni ASerra-Capizzano S(2015)Accelerated multigrid for graph Laplacian operatorsApplied Mathematics and Computation10.1016/j.amc.2015.08.033270:C(193-215)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.08.033
Peng RSpielman DShmoys D(2014)An efficient parallel solver for SDD linear systemsProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591832(333-342)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2591796.2591832
Blelloch GGupta AKoutis IMiller GPeng RTangwongsan K(2014)Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch SubgraphsTheory of Computing Systems10.1007/s00224-013-9444-555:3(521-554)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1007/s00224-013-9444-5
Show More Cited By

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

Recommendations

A linear-time algorithm for clique-coloring planar graphs
Abstract
A clique of a graph G is a set of pairwise adjacent vertices of G. A clique-coloring of G is an assignment of colors to the vertices of G such that no inclusion-wise maximal clique of size at least 2 is monochromatic. Mohar and ...
Outer 1-Planar Graphs
Abstract
A graph is outer 1-planar (o1p) if it can be drawn in the plane such that all vertices are in the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time, and specialize 1-... $\frac{}{}$ $\frac{}{} \frac{}{}$ $^{}$
Sparsified Cholesky and multigrid solvers for connection laplacians
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process. We use ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
299
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dell'Acqua PFrangioni ASerra-Capizzano S(2015)Accelerated multigrid for graph Laplacian operatorsApplied Mathematics and Computation10.1016/j.amc.2015.08.033270:C(193-215)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.08.033
Peng RSpielman DShmoys D(2014)An efficient parallel solver for SDD linear systemsProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591832(333-342)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2591796.2591832
Blelloch GGupta AKoutis IMiller GPeng RTangwongsan K(2014)Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch SubgraphsTheory of Computing Systems10.1007/s00224-013-9444-555:3(521-554)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1007/s00224-013-9444-5
Chin HMadry AMiller GPeng RKleinberg R(2013)Runtime guarantees for regression problemsProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422469(269-282)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422469
Koutis IMiller GPeng R(2012)A fast solver for a class of linear systemsCommunications of the ACM10.1145/2347736.234775955:10(99-107)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1145/2347736.2347759
Das GFraser RLòpez-Ortiz ANickerson B(2011)On the discrete unit disk cover problemProceedings of the 5th international conference on WALCOM: algorithms and computation10.5555/1966169.1966191(146-157)Online publication date: 18-Feb-2011
https://dl.acm.org/doi/10.5555/1966169.1966191
Blelloch GGupta AKoutis IMiller GPeng RTangwongsan KMeyer auf der Heide FRajaraman R(2011)Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphsProceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures10.1145/1989493.1989496(13-22)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1989493.1989496
Mustafa NRay SHershberger JFogel E(2009)PTAS for geometric hitting set problems via local searchProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542367(17-22)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542367
Sarkar PMoore AQuemada JLeón GMaarek YNejdl W(2009)Fast dynamic reranking in large graphsProceedings of the 18th international conference on World wide web10.1145/1526709.1526715(31-40)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.1145/1526709.1526715
Claude FDorrigiv RDurocher SFraser RLópez-Ortiz ASalinger A(2009)Practical Discrete Unit Disk Cover Using an Exact Line-Separable AlgorithmProceedings of the 20th International Symposium on Algorithms and Computation10.1007/978-3-642-10631-6_7(45-54)Online publication date: 5-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10631-6_7
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents