Generalized Persistence Algorithm for Decomposing Multi-parameter Persistence Modules
share
The classical persistence algorithm virtually computes the unique decomposition of a persistence module implicitly given by an input simplicial filtration. Based on matrix reduction, this algorithm is a cornerstone of the emergent area of topological data analysis. Its input is a simplicial filtration defined over integers Z giving rise to a 1-parameter persistence module. It has been recognized that multi-parameter version of persistence modules given by simplicial filtrations over d-dimensional integer grids Z^d is equally or perhaps more important in data science applications. However, in the multi-parameter setting, one of the main bottlenecks is that topological summaries such as barcodes and distances among them cannot be as efficiently computed as in the 1-parameter case because there is no known generalization of the persistence algorithm for computing the decomposition of multi-parameter persistence modules. The Meataxe algorithm, the only known one for computing such a decomposition runs in Õ(n^6(d+1)) time where n is the size of input module. We present for the first time a generalization of the persistence algorithm based on a generalized matrix reduction technique that runs in O(n^2ω) time where ω<2.373 is the exponent for matrix multiplication. We also present an O(n^d+1) algorithm to convert the input filtration to a suitable matrix called presentation matrix which is ultimately decomposed. Various structural and computational results connecting the graded modules from commutative algebra to matrix reductions are established through the course.
READ FULL TEXT