# Generalized persistence algorithm for decomposing multiparameter persistence modules

Generalized persistence algorithm for decomposing multiparameter persistence modules The classical persistence algorithm 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 the integers Z\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}$$\end{document} giving rise to a 1-parameter persistence module. It has been recognized that multiparameter version of persistence modules given by simplicial filtrations over d-dimensional integer grids Zd\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}^d$$\end{document} is equally or perhaps more important in data science applications. However, in the multiparameter setting, one of the main challenges is that topological summaries based on algebraic structure such as decompositions and bottleneck distances cannot be as efficiently computed as in the 1-parameter case because there is no known extension of the persistence algorithm to multiparameter persistence modules. We present an efficient algorithm to compute the unique decomposition of a finitely presented persistence module M defined over the multiparameter Zd\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}^d$$\end{document}. The algorithm first assumes that the module is presented with a set of N generators and relations that are distinctly graded. Based on a generalized matrix reduction technique it runs in O(N2ω+1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(N^{2\omega +1})$$\end{document} time where ω<2.373\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\omega <2.373$$\end{document} is the exponent of matrix multiplication. This is much better than the well known algorithm called Meataxe which runs in O~(N6(d+1))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\tilde{O}}(N^{6(d+1)})$$\end{document} time on such an input. In practice, persistence modules are usually induced by simplicial filtrations. With such an input consisting of n simplices, our algorithm runs in O(n(d-1)(2ω+1))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^{(d-1)(2\omega + 1)})$$\end{document} time for d≥2\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$d\ge 2$$\end{document}. For the special case of zero dimensional homology, it runs in time O(n2ω+1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^{2\omega +1})$$\end{document}. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Applied and Computational Topology Springer Journals

# Generalized persistence algorithm for decomposing multiparameter persistence modules

, Volume 6 (3) – Sep 1, 2022
52 pages      /lp/springer-journals/generalized-persistence-algorithm-for-decomposing-multiparameter-0y5j1eFsAY
Publisher
Springer Journals
Copyright © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2022
ISSN
2367-1726
eISSN
2367-1734
DOI
10.1007/s41468-022-00087-5
Publisher site
See Article on Publisher Site

### Abstract

The classical persistence algorithm 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 the integers Z\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}$$\end{document} giving rise to a 1-parameter persistence module. It has been recognized that multiparameter version of persistence modules given by simplicial filtrations over d-dimensional integer grids Zd\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}^d$$\end{document} is equally or perhaps more important in data science applications. However, in the multiparameter setting, one of the main challenges is that topological summaries based on algebraic structure such as decompositions and bottleneck distances cannot be as efficiently computed as in the 1-parameter case because there is no known extension of the persistence algorithm to multiparameter persistence modules. We present an efficient algorithm to compute the unique decomposition of a finitely presented persistence module M defined over the multiparameter Zd\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathbb {Z}}^d$$\end{document}. The algorithm first assumes that the module is presented with a set of N generators and relations that are distinctly graded. Based on a generalized matrix reduction technique it runs in O(N2ω+1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(N^{2\omega +1})$$\end{document} time where ω<2.373\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\omega <2.373$$\end{document} is the exponent of matrix multiplication. This is much better than the well known algorithm called Meataxe which runs in O~(N6(d+1))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\tilde{O}}(N^{6(d+1)})$$\end{document} time on such an input. In practice, persistence modules are usually induced by simplicial filtrations. With such an input consisting of n simplices, our algorithm runs in O(n(d-1)(2ω+1))\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^{(d-1)(2\omega + 1)})$$\end{document} time for d≥2\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$d\ge 2$$\end{document}. For the special case of zero dimensional homology, it runs in time O(n2ω+1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^{2\omega +1})$$\end{document}.

### Journal

Journal of Applied and Computational TopologySpringer Journals

Published: Sep 1, 2022

Keywords: Multiparameter persistence; Computational topology; Topological data analysis; Persistence module; Indecomposables; Matrix reduction; Presentations; 55-08; 55U30; 18G90

Access the full text.