Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes
share
We describe a nearly-linear time algorithm to solve the linear system L_1x = b parameterized by the first Betti number of the complex, where L_1 is the 1-Laplacian of a simplicial complex K that is a subcomplex of a collapsible complex X linearly embedded in ℝ^3. Our algorithm generalizes the work of Black et al. [SODA2022] that solved the same problem but required that K have trivial first homology. Our algorithm works for complexes K with arbitrary first homology with running time that is nearly-linear with respect to the size of the complex and polynomial with respect to the first Betti number. The key to our solver is a new algorithm for computing the Hodge decomposition of 1-chains of K in nearly-linear time. Additionally, our algorithm implies a nearly quadratic solver and nearly quadratic Hodge decomposition for the 1-Laplacian of any simplicial complex K embedded in ℝ^3, as K can always be expanded to a collapsible embedded complex of quadratic complexity.
READ FULL TEXT