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 $\mathbb{R}^3$ (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 $\mathbb{R}^3$.

We generalize the specialized solvers for $1$-Laplacians to simplicial complexes with additional geometric structures but \emph{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]).