research-article

Incomplete nested dissection

Authors:

Robert Schwieterman,

Peng ZhangAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 404 - 417

https://doi.org/10.1145/3188745.3188960

Published: 20 June 2018 Publication History

Abstract

We present an asymptotically faster algorithm for solving linear systems in well-structured 3-dimensional truss stiffness matrices. These linear systems arise from linear elasticity problems, and can be viewed as extensions of graph Laplacians into higher dimensions. Faster solvers for the 2-D variants of such systems have been studied using generalizations of tools for solving graph Laplacians [Daitch-Spielman CSC’07, Shklarski-Toledo SIMAX’08].

Given a 3-dimensional truss over n vertices which is formed from a union of k convex structures (tetrahedral meshes) with bounded aspect ratios, whose individual tetrahedrons are also in some sense well-conditioned, our algorithm solves a linear system in the associated stiffness matrix up to accuracy є in time O(k^1/3 n^5/3 log(1 / є)). This asymptotically improves the running time O(n²) by Nested Dissection for all k ≪ n.

We also give a result that improves on Nested Dissection even when we allow any aspect ratio for each of the k convex structures (but we still require well-conditioned individual tetrahedrons). In this regime, we improve on Nested Dissection for k ≪ n^1/44.

The key idea of our algorithm is to combine nested dissection and support theory. Both of these techniques for solving linear systems are well studied, but usually separately. Our algorithm decomposes a 3-dimensional truss into separate and balanced regions with small boundaries. We then bound the spectrum of each such region separately, and utilize such bounds to obtain improved algorithms by preconditioning with partial states of separator-based Gaussian elimination.

Supplementary Material

MP4 File (3c-5.mp4)

Download
32.82 MB

References

[1]

{Axe85} Owe Axelsson. A survey of preconditioned iterative methods for linear systems of algebraic equations. BIT Numerical Mathematics, 25(1):165– 187, 1985.

[2]

{BCFN16} Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri. Minimum cycle and homology bases of surface embedded graphs. arXiv preprint arXiv:1607.05112, 2016.

[3]

{BEG94} Marshall Bern, David Eppstein, and John Gilbert. Provably good mesh generation. Journal of Computer and System Sciences, 48(3):384–409, 1994.

Digital Library

[4]

STOC’18, June 25–29, 2018, Los Angeles, CA, USA Rasmus Kyng, Richard Peng, Robert Schwieterman, and Peng Zhang

[5]

{BENWN14} Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. All-pairs minimum cuts in near-linear time for surface-embedded graphs. arXiv preprint arXiv:1411.7055, 2014.

[6]

{BHP01} Gill Barequet and Sariel Har-Peled. Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms, 38(1):91–109, January 2001.

Digital Library

[7]

{BKM + 11a} Glencora Borradaile, Philip N Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 170–179. IEEE, 2011.

Digital Library

[8]

{BKM + 11b} Glencora Borradaile, Philip N Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 170–179. IEEE, 2011. Available at: https://arxiv.org/abs/1105.2228.

Digital Library

[9]

{BSS13} Afonso S Bandeira, Amit Singer, and Daniel A Spielman. A cheeger inequality for the graph connection laplacian. SIAM Journal on Matrix Analysis and Applications, 34(4):1611–1630, 2013.

[10]

{CFM + 14} Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Richard Peng, and Noel Walkington. Solving 1-laplacians in nearly linear time: Collapsing and expanding a topological ball. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 204–216, 2014. Available at: https://www.cs.cmu.edu/~glmiller/Publications/Papers/CoFMNPW14.pdf. {Che89} L Paul Chew. Guaranteed-quality triangular meshes. Technical report, Cornell University, 1989.

[11]

{Chu96} Fan RK Chung. Laplacians of graphs and cheegerâĂŹs inequalities. Combinatorics, Paul Erdos is Eighty, 2(157-172):13–2, 1996.

[12]

{CKM + 14} Michael B Cohen, Rasmus Kyng, Gary L Miller, Jakub W Pachocki, Richard Peng, Anup B Rao, and Shen Chen Xu. Solving sdd linear systems in nearly m log 1/2 n time. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 343–352. ACM, 2014.

Digital Library

[13]

{CKP + 17} Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 410–419, New York, NY, USA, 2017. ACM.

Digital Library

[14]

{DS07} Samuel I Daitch and Daniel A Spielman. Support-graph preconditioners for 2-dimensional trusses. arXiv preprint cs/0703119, 2007.

[15]

{EN11} Jeff Erickson and Amir Nayyeri. Computing replacement paths in surface embedded graphs. In Proceedings of the twenty-second annual ACMSIAM symposium on Discrete Algorithms, pages 1347–1354. Society for Industrial and Applied Mathematics, 2011.

Digital Library

[16]

{Fed64} Radii Petrovich Fedorenko. The speed of convergence of one iterative process. USSR Computational Mathematics and Mathematical Physics, 4(3):227–235, 1964.

[17]

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

Digital Library

[18]

{Geo73} Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345–363, 1973.

Digital Library

[19]

{GNP94} John R Gilbert, Esmond G Ng, and Barry W Peyton. An efficient algorithm to compute row and column counts for sparse cholesky factorization. SIAM Journal on Matrix Analysis and Applications, 15(4):1075–1091, 1994.

Digital Library

[20]

{Goo95} Michael T Goodrich. Planar separators and parallel polygon triangulation. Journal of Computer and System Sciences, 51(3):374–389, 1995.

Digital Library

[21]

{HKRS97} Monika R Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian. Faster shortest-path algorithms for planar graphs. journal of computer and system sciences, 55(1):3–23, 1997.

Digital Library

[22]

{KLP + 16} Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. Sparsified cholesky and multigrid solvers for connection laplacians. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 842–850, New York, NY, USA, 2016. ACM.

Digital Library

[23]

{KMP10} Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS ’10, pages 235–244, Washington, DC, USA, 2010. IEEE Computer Society. Available at http://arxiv.org/abs/1003.2958.

Digital Library

[24]

{KMP11} Ioannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log n time solver for SDD linear systems. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, pages 590–598, Washington, DC, USA, 2011. IEEE Computer Society. Available at http://arxiv.org/abs/1102.4842.

Digital Library

[25]

{KMS13} Philip N Klein, Shay Mozes, and Christian Sommer. Structured recursive separator decompositions for planar graphs in linear time. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 505–514. ACM, 2013.

Digital Library

[26]

{KS16} Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians-fast, sparse, and simple. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 573–582. IEEE, 2016.

[27]

{KZ17} Rasmus Kyng and Peng Zhang. Hardness results for structured linear systems. arXiv preprint arXiv:1705.02944, 2017.

[28]

{LG14} François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296–303. ACM, 2014. Available at: https://arxiv.org/abs/1401.7714.

Digital Library

[29]

{LGT14} James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM ( JACM), 61(6):37, 2014.

Digital Library

[30]

{LRT79} Richard J Lipton, Donald J Rose, and Robert Endre Tarjan. Generalized nested dissection. SIAM journal on numerical analysis, 16(2):346–358, 1979.

[31]

{ŁS11} Jakub Łącki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in o (n loglogn) time. In European Symposium on Algorithms, pages 155–166. Springer, 2011.

Digital Library

[32]

{MT90} Gary L Miller and William Thurston. Separators in two and three dimensions. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 300–309. ACM, 1990.

Digital Library

[33]

{MT TV98} Gary L Miller, Shang-Hua Teng, William Thurston, and Stephen A Vavasis. Geometric separators for finite-element meshes. SIAM Journal on Scientific Computing, 19(2):364–386, 1998.

Digital Library

[34]

{MV92} Scott A Mitchell and Stephen A Vavasis. Quality mesh generation in three dimensions. In Proceedings of the eighth annual symposium on Computational geometry, pages 212–221. ACM, 1992.

Digital Library

[35]

{PRT16} Ori Parzanchevski, Ron Rosenthal, and Ran J Tessler. Isoperimetric inequalities in simplicial complexes. Combinatorica, 36(2):195–227, 2016.

Digital Library

[36]

{PS14} Richard Peng and Daniel A Spielman. An efficient parallel solver for sdd linear systems. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 333–342. ACM, 2014.

Digital Library

[37]

{Rup93} Jim Ruppert. A new and simple algorithm for quality 2-dimensional mesh generation. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pages 83–92. Society for Industrial and Applied Mathematics, 1993.

Digital Library

[38]

{Saa03} Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003.

[39]

{SF73} Gilbert Strang and George J Fix. An analysis of the finite element method, volume 212. Prentice-hall Englewood Cliffs, NJ, 1973.

[40]

{SKM14} John Steenbergen, Caroline Klivans, and Sayan Mukherjee. A cheegertype inequality on simplicial complexes. Advances in Applied Mathematics, 56:56–77, 2014.

[41]

{ST08} Gil Shklarski and Sivan Toledo. Rigidity in finite-element matrices: Sufficient conditions for the rigidity of structures and substructures. SIAM Journal on Matrix Analysis and Applications, 30(1):7–40, 2008.

Digital Library

[42]

{ST14} Daniel A Spielman and Shang-Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications, 35(3):835– 885, 2014.

Digital Library

Cited By

Chen JGao YHuang YPeng RWang R(2023)Hardness of Graph-Structured Algebraic and Symbolic ProblemsAlgorithms and Data Structures10.1007/978-3-031-38906-1_16(232-246)Online publication date: 28-Jul-2023
https://doi.org/10.1007/978-3-031-38906-1_16
Cohen MLee YSong Z(2021)Solving Linear Programs in the Current Matrix Multiplication TimeJournal of the ACM10.1145/342430568:1(1-39)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1145/3424305
Dong SLee YYe GKhuller SVassilevska Williams V(2021)A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central pathProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451056(1784-1797)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451056
Show More Cited By

Index Terms

Incomplete nested dissection
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Preconditioners for Generalized Saddle-Point Problems

\noindent We propose and examine block-diagonal preconditioners and variants of indefinite preconditioners for block two-by-two generalized saddle-point problems. That is, we consider the nonsymmetric, nonsingular case where the (2,2) block is small in ...
Matrix sparsification and nested dissection over arbitrary fields

The generalized nested dissection method, developed by Lipton et al. [1979], is a seminal method for solving a linear system Ax=b where A is a symmetric positive definite matrix. The method runs extremely fast whenever A is a well-separable matrix (such ...
Hypergraph-Based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization

In this paper we discuss a hypergraph-based unsymmetric nested dissection (HUND) ordering for reducing the fill-in incurred during Gaussian elimination. It has several important properties. It takes a global perspective of the entire matrix, as opposed ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,301 of 4,174 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
182
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)4

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen JGao YHuang YPeng RWang R(2023)Hardness of Graph-Structured Algebraic and Symbolic ProblemsAlgorithms and Data Structures10.1007/978-3-031-38906-1_16(232-246)Online publication date: 28-Jul-2023
https://doi.org/10.1007/978-3-031-38906-1_16
Cohen MLee YSong Z(2021)Solving Linear Programs in the Current Matrix Multiplication TimeJournal of the ACM10.1145/342430568:1(1-39)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1145/3424305
Dong SLee YYe GKhuller SVassilevska Williams V(2021)A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central pathProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451056(1784-1797)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451056
Cohen MLee YSong ZCharikar MCohen E(2019)Solving linear programs in the current matrix multiplication timeProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316303(938-942)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316303

View Options

Get Access

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