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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2019
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
AKLM-JMIV2018.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 2.09 MB