%0 Journal Article
%T Computing Multidimensional Persistence
%A Gunnar Carlsson
%A Gurjeet Singh
%A Afra J. Zomorodian
%J Journal of Computational Geometry
%D 2010
%I Carleton University
%X 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.
%U http://jocg.org/index.php/jocg/article/view/19