Computing multidimensional persistence
<p>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 multidime...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Carleton University
2010-11-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | http://jocg.org/index.php/jocg/article/view/19 |
| _version_ | 1818582090885627904 |
|---|---|
| author | Gunnar Carlsson Gurjeet Singh Afra J. Zomorodian |
| author_facet | Gunnar Carlsson Gurjeet Singh Afra J. Zomorodian |
| author_sort | Gunnar Carlsson |
| collection | DOAJ |
| description | <p>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.</p> |
| first_indexed | 2024-12-16T07:43:52Z |
| format | Article |
| id | doaj.art-42c11cd19726436ba85f6ebcecaa2c52 |
| institution | Directory Open Access Journal |
| issn | 1920-180X |
| language | English |
| last_indexed | 2024-12-16T07:43:52Z |
| publishDate | 2010-11-01 |
| publisher | Carleton University |
| record_format | Article |
| series | Journal of Computational Geometry |
| spelling | doaj.art-42c11cd19726436ba85f6ebcecaa2c522022-12-21T22:39:00ZengCarleton UniversityJournal of Computational Geometry1920-180X2010-11-011110.20382/jocg.v1i1a610Computing multidimensional persistenceGunnar Carlsson0Gurjeet Singh1Afra J. Zomorodian2Stanford UniversityStanford UniversityDartmouth College<p>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.</p>http://jocg.org/index.php/jocg/article/view/19 |
| spellingShingle | Gunnar Carlsson Gurjeet Singh Afra J. Zomorodian Computing multidimensional persistence Journal of Computational Geometry |
| title | Computing multidimensional persistence |
| title_full | Computing multidimensional persistence |
| title_fullStr | Computing multidimensional persistence |
| title_full_unstemmed | Computing multidimensional persistence |
| title_short | Computing multidimensional persistence |
| title_sort | computing multidimensional persistence |
| url | http://jocg.org/index.php/jocg/article/view/19 |
| work_keys_str_mv | AT gunnarcarlsson computingmultidimensionalpersistence AT gurjeetsingh computingmultidimensionalpersistence AT afrajzomorodian computingmultidimensionalpersistence |