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 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\omega  }) time  where \omega<2.373 is the exponent for matrix multiplication . We also show how a recent algorithm of Lesnick and Wright can be adapted to convert the input filtration in O(n^{2d+1 presentation matrix %DIFAUXCMD which is ultimately decomposed . 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^{ 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) where \omega<2.373 is the exponent for matrix multiplication %DIFAUXCMD . Various structural and computational results connecting the graded modules from commutative algebra to matrix reductions are established through the course.
D
,
R
6(d+1)
12d
R
module
filtration
A
+1
A
for d=2 and in O(n^{d(2\omega +1)
D
. We also show how a recent algorithm of Lesnick and Wright can be adapted to convert the input filtration in O(n^{2d+1
D
presentation matrix
D
which is ultimately decomposed