2026-07-25T03:04:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16364 2024-03-06T10:57:17Z ddc:004 open_access

Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes Black, Mitchell Nayyeri, Amir Computational Topology Laplacian solvers Combinatorial Laplacian Hodge decomposition Parameterized Complexity We describe a nearly-linear time algorithm to solve the linear system L₁x = b parameterized by the first Betti number of the complex, where L₁ is the 1-Laplacian of a simplicial complex K that is a subcomplex of a collapsible complex X linearly embedded in ℝ³. 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 ℝ³, as K can always be expanded to a collapsible embedded complex of quadratic complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mitchell Black and Amir Nayyeri 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.23 urn:nbn:de:0030-drops-163641 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.23 eng https://creativecommons.org/licenses/by/4.0/legalcode