Computing multidimensional persistence

Gunnar Carlsson, Gurjeet Singh, Afra J. Zomorodian

Abstract


The theory of multidimensional persistence captures the topology of a multifiltration - a multiparameter family of increasing spaces.  Multifiltrations arise naturally in the topological analysis of scientific data.  In this paper, we give a polynomial time algorithm for computing multidimensional persistence.  We recast this computation as a problem within computational commutative algebra and utilize algorithms from this area to solve it.  While the resulting problem is EXPSPACE-complete and the standard algorithms take doubly-exponential time, we exploit the structure inherent withing multifiltrations to yield practical algorithms.  We implement all algorithms in the paper and provide statistical experiments to demonstrate their feasibility.


Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v1i1a6

ISSN: 1920-180X