Incomplete nested dissection

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.

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.
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.
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.
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.
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.
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.
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.
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.
18. {Geo73} Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345–363, 1973.
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.
20. {Goo95} Michael T Goodrich. Planar separators and parallel polygon triangulation. Journal of Computer and System Sciences, 51(3):374–389, 1995.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
35. {PRT16} Ori Parzanchevski, Ron Rosenthal, and Ran J Tessler. Isoperimetric inequalities in simplicial complexes. Combinatorica, 36(2):195–227, 2016.
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.
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.
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.
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.

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Computations on matrices

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry