2022/05/04 by Black, Mitchell, Nayyeri, Amir
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2205.02134
We describe a nearly-linear time algorithm to solve the linear system L1x = b parameterized by the first Betti number of the complex, where L1 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.