License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.41
URN: urn:nbn:de:0030-drops-186947
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18694/
Ding, Ming ;
Zhang, Peng
Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences
Abstract
We present efficient algorithms for solving systems of linear equations in 1-Laplacians of well-shaped simplicial complexes. 1-Laplacians, or higher-dimensional Laplacians, generalize graph Laplacians to higher-dimensional simplicial complexes and play a key role in computational topology and topological data analysis. Previously, nearly-linear time solvers were developed for simplicial complexes with known collapsing sequences and bounded Betti numbers, such as those triangulating a three-ball in ℝ³ (Cohen, Fasy, Miller, Nayyeri, Peng, and Walkington [SODA'2014], Black, Maxwell, Nayyeri, and Winkelman [SODA'2022], Black and Nayyeri [ICALP'2022]). Furthermore, Nested Dissection provides quadratic time solvers for more general systems with nonzero structures representing well-shaped simplicial complexes embedded in ℝ³.
We generalize the specialized solvers for 1-Laplacians to simplicial complexes with additional geometric structures but without collapsing sequences and bounded Betti numbers, and we improve the runtime of Nested Dissection. We focus on simplicial complexes that meet two conditions: (1) each individual simplex has a bounded aspect ratio, and (2) they can be divided into "disjoint" and balanced regions with well-shaped interiors and boundaries. Our solvers draw inspiration from the Incomplete Nested Dissection for stiffness matrices of well-shaped trusses (Kyng, Peng, Schwieterman, and Zhang [STOC'2018]).
BibTeX - Entry
@InProceedings{ding_et_al:LIPIcs.ESA.2023.41,
author = {Ding, Ming and Zhang, Peng},
title = {{Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {41:1--41:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18694},
URN = {urn:nbn:de:0030-drops-186947},
doi = {10.4230/LIPIcs.ESA.2023.41},
annote = {Keywords: 1-Laplacian Solvers, Simplicial Complexes, Incomplete Nested Dissection}
}
|
Keywords: |
|
1-Laplacian Solvers, Simplicial Complexes, Incomplete Nested Dissection |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
