JoCG paper

New paper published in JoCG:


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.