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, a popular one known for computing such a decomposition runs in O(n^{ 12d }) time where n is the size of the input filtration. 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\omega+1}) time for d=2 and in O(n^{d(2\omega +1)}) time for d>2 where \omega<2.373 is the exponent for matrix multiplication. Various structural and computational results connecting the graded modules from commutative algebra to matrix reductions are established through the course.
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, a popular one known for computing such a decomposition runs in O(n^{ 6(d+1) }) time where n is the size of the input filtration. 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\omega+1}) time for d=2 and in O(n^{d(2\omega +1)}) time for d>2 where \omega<2.373 is the exponent for matrix multiplication. Various structural and computational results connecting the graded modules from commutative algebra to matrix reductions are established through the course.
R
12d
6(d+1)