License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.37
URN: urn:nbn:de:0030-drops-104413
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10441/
Go to the corresponding LIPIcs Volume Portal

Fugacci, Ulderico ; Kerber, Michael

Chunk Reduction for Multi-Parameter Persistent Homology

pdf-format:
LIPIcs-SoCG-2019-37.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{fugacci_et_al:LIPIcs:2019:10441,
  author =	{Ulderico Fugacci and Michael Kerber},
  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 =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10441},
  URN =		{urn:nbn:de:0030-drops-104413},
  doi =		{10.4230/LIPIcs.SoCG.2019.37},
  annote =	{Keywords: Multi-parameter persistent homology, Matrix reduction, Chain complexes}
}

Keywords: Multi-parameter persistent homology, Matrix reduction, Chain complexes
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

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