License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.23
URN: urn:nbn:de:0030-drops-163641
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16364/
Go to the corresponding LIPIcs Volume Portal

Black, Mitchell ; Nayyeri, Amir

Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes

pdf-format:
LIPIcs-ICALP-2022-23.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{black_et_al:LIPIcs.ICALP.2022.23,
  author =	{Black, Mitchell and Nayyeri, Amir},
  title =	{{Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16364},
  URN =		{urn:nbn:de:0030-drops-163641},
  doi =		{10.4230/LIPIcs.ICALP.2022.23},
  annote =	{Keywords: Computational Topology, Laplacian solvers, Combinatorial Laplacian, Hodge decomposition, Parameterized Complexity}
}

Keywords: Computational Topology, Laplacian solvers, Combinatorial Laplacian, Hodge decomposition, Parameterized Complexity
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI