Computing Multidimensional Persistence
Gunnar Carlsson, Singh, Gurjeet, Afra Zomorodian · arXiv (Cornell University) · 2009
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 algebraic geometry 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.