Given a simplicial complex and a vector-valued function on its vertices, we present an algorithmic construction of an acyclic partial matching on the cells of the complex compatible with the given function. This implies the construction can be used to build a reduced filtered complex with the same multidimensional persistent homology as of the original one filtered by the sublevel sets of the function. The correctness of the algorithm is proved, and its complexity is analyzed. A combinatorial interpretation of our algorithm based on the concept of a multidimensional discrete Morse function is introduced for the first time in this paper. Numerical experiments show a substantial rate of reduction in the number of cells achieved by the algorithm.

Acyclic Partial Matchings for Multidimensional Persistence: Algorithm and Combinatorial Interpretation / Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia; Masoni, Filippo. - In: JOURNAL OF MATHEMATICAL IMAGING AND VISION. - ISSN 0924-9907. - 61:2(2019), pp. 174-192. [10.1007/s10851-018-0843-8]

Acyclic Partial Matchings for Multidimensional Persistence: Algorithm and Combinatorial Interpretation

Landi, Claudia;
2019

Abstract

Given a simplicial complex and a vector-valued function on its vertices, we present an algorithmic construction of an acyclic partial matching on the cells of the complex compatible with the given function. This implies the construction can be used to build a reduced filtered complex with the same multidimensional persistent homology as of the original one filtered by the sublevel sets of the function. The correctness of the algorithm is proved, and its complexity is analyzed. A combinatorial interpretation of our algorithm based on the concept of a multidimensional discrete Morse function is introduced for the first time in this paper. Numerical experiments show a substantial rate of reduction in the number of cells achieved by the algorithm.
27-ago-2018
61
2
174
192
Acyclic Partial Matchings for Multidimensional Persistence: Algorithm and Combinatorial Interpretation / Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia; Masoni, Filippo. - In: JOURNAL OF MATHEMATICAL IMAGING AND VISION. - ISSN 0924-9907. - 61:2(2019), pp. 174-192. [10.1007/s10851-018-0843-8]
Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia; Masoni, Filippo
File in questo prodotto:
File Dimensione Formato  
AKLM-JMIV2018.pdf

non disponibili

Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 2.09 MB
Formato Adobe PDF
2.09 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1165089
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 1
social impact