Weighted 1-Laplacian Solvers for Well-Shaped Simplicial Complexes
share
We present efficient algorithms for solving systems of linear equations in weighted 1-Laplacians of well-shaped simplicial complexes. 1- or higher-dimensional Laplacians generalize graph Laplacians to higher-dimensional simplicial complexes. Previously, nearly-linear time solvers were designed for unweighted simplicial complexes that triangulate a three-ball in ℝ^3 (Cohen, Fasy, Miller, Nayyeri, Peng, and Walkington [SODA'2013]) and their sub-complexes (Black, Maxwell, Nayyeri, and Winkelman [SODA'2022], Black and Nayyeri [ICALP'2022]). Additionally, quadratic time solvers by Nested Dissection exist for more general systems whose nonzero structures encode well-shaped simplicial complexes embedded in ℝ^3. We generalize the specialized solvers for 1-Laplacians to weighted simplicial complexes with additional geometric structures and improve the runtime of Nested Dissection. Specifically, we consider simplicial complexes embedded in ℝ^3 such that: (1) the complex triangulates a convex ball in ℝ^3, (2) the underlying topological space of the complex is convex and has a bounded aspect ratio, and (3) each tetrahedron has a bounded aspect ratio and volume. We say such a simplicial complex is stable. We can approximately solve weighted 1-Laplacian systems in a stable simplicial complex with n simplexes up to high precision in time Õ (n^3/2) if the ratio between the maximum and minimum simplex weights is Õ(n^1/6). In addition, we generalize this solver to a union of stable simplicial complex chunks. As a result, our solver has a comparable runtime, parameterized by the number of chunks and the number of simplexes shared by more than one chunk. Our solvers are inspired by the Incomplete Nested Dissection designed by Kyng, Peng, Schwieterman, and Zhang [STOC'2018] for stiffness matrices of well-shaped trusses.
READ FULL TEXT