1 Search Results for "Fugacci, Ulderico"

Document
DOI: 10.4230/LIPIcs.SoCG.2019.37
Chunk Reduction for Multi-Parameter Persistent Homology

Authors: Ulderico Fugacci and Michael Kerber

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
The extension of persistent homology to multi-parameter setups is an algorithmic challenge. Since most computation tasks scale badly with the size of the input complex, an important pre-processing step consists of simplifying the input while maintaining the homological information. We present an algorithm that drastically reduces the size of an input. Our approach is an extension of the chunk algorithm for persistent homology (Bauer et al., Topological Methods in Data Analysis and Visualization III, 2014). We show that our construction produces the smallest multi-filtered chain complex among all the complexes quasi-isomorphic to the input, improving on the guarantees of previous work in the context of discrete Morse theory. Our algorithm also offers an immediate parallelization scheme in shared memory. Already its sequential version compares favorably with existing simplification schemes, as we show by experimental evaluation.
Cite as

Ulderico Fugacci and Michael Kerber. Chunk Reduction for Multi-Parameter Persistent Homology. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fugacci_et_al:LIPIcs.SoCG.2019.37,
  author =	{Fugacci, Ulderico and Kerber, Michael},
  title =	{{Chunk Reduction for Multi-Parameter Persistent Homology}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.37},
  URN =		{urn:nbn:de:0030-drops-104413},
  doi =		{10.4230/LIPIcs.SoCG.2019.37},
  annote =	{Keywords: Multi-parameter persistent homology, Matrix reduction, Chain complexes}
}
  • Refine by Author
  • 1 Fugacci, Ulderico
  • 1 Kerber, Michael

  • Refine by Classification
  • 1 Computing methodologies → Shared memory algorithms
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 Chain complexes
  • 1 Matrix reduction
  • 1 Multi-parameter persistent homology

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact