{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T01:49:57Z","timestamp":1778032197593,"version":"3.51.4"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T00:00:00Z","timestamp":1623888000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T00:00:00Z","timestamp":1623888000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SFB-TR-109"],"award-info":[{"award-number":["SFB-TR-109"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Appl. and Comput. Topology"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present an algorithm for the computation of Vietoris\u2013Rips persistence barcodes and describe its implementation in the software Ripser. The method relies on implicit representations of the coboundary operator and the filtration order of the simplices, avoiding the explicit construction and storage of the filtration coboundary matrix. Moreover, it makes use of apparent pairs, a simple but powerful method for constructing a discrete gradient field from a total order on the simplices of a simplicial complex, which is also of independent interest. Our implementation shows substantial improvements over previous software both in time and memory usage.<\/jats:p>","DOI":"10.1007\/s41468-021-00071-5","type":"journal-article","created":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T19:03:01Z","timestamp":1623956581000},"page":"391-423","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":243,"title":["Ripser: efficient computation of Vietoris\u2013Rips persistence barcodes"],"prefix":"10.1007","volume":"5","author":[{"given":"Ulrich","family":"Bauer","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"71_CR1","unstructured":"Barannikov, S.A.: The framed Morse complex and its invariants. In: Singularities and Bifurcations, Volume\u00a021 of Advances in Soviet Mathematics, pp. 93\u2013115. American Mathematical Society, Providence (1994)"},{"key":"71_CR2","unstructured":"Bauer, U.: Ripser: a lean C++ code for the computation of Vietoris\u2013Rips persistence barcodes (2016). http:\/\/ripser.org"},{"key":"71_CR3","unstructured":"Bauer, U., Schmahl, M.: Lifespan functors and natural dualities in persistent homology. Preprint (2020). arXiv: 2012.12881"},{"key":"71_CR4","doi-asserted-by":"crossref","unstructured":"Bauer, U., Kerber, M., Reininghaus, J.: Distributed computation of persistent homology. In: Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 31\u201338. SIAM (2014). Software available at https:\/\/github.com\/DIPHA\/dipha","DOI":"10.1137\/1.9781611973198.4"},{"key":"71_CR5","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jsc.2016.03.008","volume":"78","author":"U Bauer","year":"2016","unstructured":"Bauer, U., Kerber, M., Reininghaus, J., Wagner, H.: PHAT\u2014persistent homology algorithms toolbox. J. Symb. Comput. 78, 76\u201390 (2016)","journal-title":"J. Symb. Comput."},{"key":"71_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.entcs.2014.06.011","volume":"306","author":"J Binchi","year":"2014","unstructured":"Binchi, J., Merelli, E., Rucco, M., Petri, G., Vaccarino, F.: jHoles: a tool for understanding biological complex networks via clique weight rank persistent homology. Electron. Notes Theor. Comput. Sci. 306, 5\u201318 (2014)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"71_CR7","doi-asserted-by":"crossref","unstructured":"Chazal, F., de Silva, V., Glisse, M., Oudot, S.: The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics. Springer (2016)","DOI":"10.1007\/978-3-319-42545-0"},{"key":"71_CR8","unstructured":"Chen, C., Kerber, M.: Persistent homology computation with a twist. In: 27th European Workshop on Computational Geometry (EuroCG), pp. 197\u2013200 (2011)"},{"issue":"4","key":"71_CR9","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.comgeo.2012.02.010","volume":"46","author":"C Chen","year":"2013","unstructured":"Chen, C., Kerber, M.: An output-sensitive algorithm for persistent homology. Comput. Geom. 46(4), 435\u2013447 (2013)","journal-title":"Comput. Geom."},{"key":"71_CR10","doi-asserted-by":"crossref","unstructured":"Cohen-Steiner, D., Edelsbrunner, H., Morozov, D.: Vines and vineyards by updating persistence in linear time. In: SCG \u201906: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, pp. 119\u2013126 (2006)","DOI":"10.1145\/1137856.1137877"},{"issue":"5","key":"71_CR11","doi-asserted-by":"publisher","first-page":"1550066+","DOI":"10.1142\/S0219498815500668","volume":"14","author":"W Crawley-Boevey","year":"2015","unstructured":"Crawley-Boevey, W.: Decomposition of pointwise finite-dimensional persistence modules. J. Algebra Appl. 14(5), 1550066+ (2015)","journal-title":"J. Algebra Appl."},{"issue":"54","key":"71_CR12","doi-asserted-by":"publisher","first-page":"2614","DOI":"10.21105\/joss.02614","volume":"5","author":"M \u010cufar","year":"2020","unstructured":"\u010cufar, M.: Ripserer.jl: flexible and efficient persistent homology computation in Julia. J. Open Source Softw. 5(54), 2614 (2020)","journal-title":"J. Open Source Softw."},{"issue":"4","key":"71_CR13","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s00454-011-9344-x","volume":"45","author":"V de Silva","year":"2011","unstructured":"de Silva, V., Morozov, D., Vejdemo-Johansson, M.: Persistent cohomology and circular coordinates. Discrete Comput. Geom. 45(4), 737\u2013759 (2011a)","journal-title":"Discrete Comput. Geom."},{"issue":"12","key":"71_CR14","doi-asserted-by":"publisher","first-page":"124003, 17","DOI":"10.1088\/0266-5611\/27\/12\/124003","volume":"27","author":"V de Silva","year":"2011","unstructured":"de Silva, V., Morozov, D., Vejdemo-Johansson, M.: Dualities in persistent (co)homology. Inverse Probl. 27(12), 124003, 17 (2011b)","journal-title":"Inverse Probl."},{"issue":"3","key":"71_CR15","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1109\/TPAMI.2014.2346172","volume":"37","author":"O Delgado-Friedrichs","year":"2015","unstructured":"Delgado-Friedrichs, O., Robins, V., Sheppard, A.: Skeletonization and partitioning of digital images using discrete Morse theory. IEEE Trans. Pattern Anal. Mach. Intell. 37(3), 654\u2013666 (2015)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"71_CR16","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., Harer, J.: Computational Topology: An Introduction. American Mathematical Society (2010)","DOI":"10.1090\/mbk\/069"},{"issue":"4","key":"71_CR17","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s00454-002-2885-2","volume":"28","author":"H Edelsbrunner","year":"2002","unstructured":"Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28(4), 511\u2013533 (2002)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"71_CR18","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1006\/aima.1997.1650","volume":"134","author":"R Forman","year":"1998","unstructured":"Forman, R.: Morse theory for cell complexes. Adv. Math. 134(1), 90\u2013145 (1998)","journal-title":"Adv. Math."},{"key":"71_CR19","doi-asserted-by":"crossref","unstructured":"Gromov, M.: Hyperbolic groups. In: Essays in group theory, Volume\u00a08 of Mathematical Sciences Research Institute Publications, pp. 75\u2013263. Springer, New York (1987)","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"71_CR20","doi-asserted-by":"crossref","unstructured":"Hausmann, J.-C.: On the Vietoris\u2013Rips complexes and a cohomology theory for metric spaces. In: Prospects in Topology (Princeton, NJ, 1994), Volume 138 of Annals of Mathematics Studies, pp. 175\u2013188. Princeton University Press, Princeton, NJ (1995)","DOI":"10.1515\/9781400882588-013"},{"key":"71_CR21","unstructured":"Henselman, G., Ghrist, R.: Matroid filtrations and computational persistent homology. arXiv preprint (2016). arXiv: 1606.00199. Software available at http:\/\/gregoryhenselman.org\/eirene\/"},{"key":"71_CR22","unstructured":"Henselman-Petrusek, G.: Matroids and Canonical Forms: Theory and Applications. Ph.D. Thesis, University of Pennsylvania (2017)"},{"key":"71_CR23","unstructured":"Huber, S.: Libstick: a C++ library to compute persistent homology (2013). https:\/\/www.sthu.org\/code\/libstick\/"},{"key":"71_CR24","doi-asserted-by":"crossref","unstructured":"J\u00f6llenbeck, M., Welker, V.: Minimal resolutions via algebraic discrete Morse theory. Mem. Am. Math. Soc. 197(923), vi+74 (2009)","DOI":"10.1090\/memo\/0923"},{"issue":"3","key":"71_CR25","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s00454-010-9319-3","volume":"45","author":"M Kahle","year":"2011","unstructured":"Kahle, M.: Random geometric complexes. Discrete Comput. Geom. 45(3), 553\u2013573 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"71_CR26","unstructured":"Knuth, D.E.: Generating all combinations. In: The Art of Computer Programming, volume 4A: Combinatorial Algorithms, Part 1, chapter 7.2.1.3, pp. 355\u2013389. Addison-Wesley Professional (2011)"},{"issue":"12","key":"71_CR27","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1016\/j.crma.2005.04.036","volume":"340","author":"DN Kozlov","year":"2005","unstructured":"Kozlov, D.N.: Discrete Morse theory for free chain complexes. C. R. Math. Acad. Sci. Paris 340(12), 867\u2013872 (2005)","journal-title":"C. R. Math. Acad. Sci. Paris"},{"key":"71_CR28","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal Jr","year":"1956","unstructured":"Kruskal Jr., J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"71_CR29","unstructured":"Lampret, L.: Chain complex reduction via fast digraph traversal. Preprint (2020). arXiv: 1903.00783"},{"issue":"6","key":"71_CR30","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1007\/PL00000526","volume":"77","author":"J Latschev","year":"2001","unstructured":"Latschev, J.: Vietoris\u2013Rips complexes of metric spaces near a closed Riemannian manifold. Arch. Math. (Basel) 77(6), 522\u2013528 (2001)","journal-title":"Arch. Math. (Basel)"},{"key":"71_CR31","unstructured":"Lewis, R.H.: CTL: The Computational Topology Library (2013). http:\/\/ctl.appliedtopology.org"},{"key":"71_CR32","unstructured":"Mendoza-Smith, R., Tanner, J.: Parallel multi-scale reduction of persistent homology filtrations. arXiv preprint (2017). arXiv: 1708.04710. Software available at https:\/\/github.com\/rodrgo\/OpenPH"},{"key":"71_CR33","doi-asserted-by":"crossref","unstructured":"Milosavljevi\u0107, N., Morozov, D., \u0160kraba, P.: Zigzag persistent homology in matrix multiplication time. In: SoCG \u201911: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, pp. 216\u2013225. ACM, New York (2011)","DOI":"10.1145\/1998196.1998229"},{"key":"71_CR34","unstructured":"Morozov, D.: Dionysus: a C++ library for computing persistent homology (2006). http:\/\/www.mrzv.org\/software\/dionysus"},{"key":"71_CR35","unstructured":"Morozov, D.: Dionysus 2: a computational topology package focused on persistent homology (2014). http:\/\/www.mrzv.org\/software\/dionysus2"},{"key":"71_CR36","unstructured":"Morozov, D., Edelsbrunner, H.: Persistent homology. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, Chapter 24, 3rd edn. CRC Press (2017)"},{"key":"71_CR37","doi-asserted-by":"crossref","unstructured":"Morozov, D., Nigmetov, A.: Towards lockfree persistent homology. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201920, pp. 555\u2013557. Association for Computing Machinery (2020)","DOI":"10.1145\/3350755.3400244"},{"key":"71_CR38","unstructured":"Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley (1984)"},{"key":"71_CR39","unstructured":"Nanda, V.: Perseus, the persistent homology software (2010). http:\/\/people.maths.ox.ac.uk\/nanda\/perseus\/index.html"},{"key":"71_CR40","doi-asserted-by":"crossref","unstructured":"Olver, S., Townsend, A.: A practical framework for infinite-dimensional linear algebra. In: Proceedings of the 1st First Workshop for High Performance Technical Computing in Dynamic Languages, HPTCDL \u201914, pp. 57\u201362. IEEE Press (2014)","DOI":"10.1109\/HPTCDL.2014.10"},{"issue":"1","key":"71_CR41","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1140\/epjds\/s13688-017-0109-5","volume":"6","author":"N Otter","year":"2017","unstructured":"Otter, N., Porter, M.A., Tillmann, U., Grindrod, P., Harrington, H.A.: A roadmap for the computation of persistent homology. EPJ Data Sci. 6(1), 17 (2017)","journal-title":"EPJ Data Sci."},{"key":"71_CR42","first-page":"45","volume":"25","author":"E Pascal","year":"1887","unstructured":"Pascal, E.: Sopra una formola numerica. G. Mat. 25, 45\u201349 (1887)","journal-title":"G. Mat."},{"key":"71_CR43","unstructured":"Perry, P., de\u00a0Silva, V., Kettner, L., Zomorodian, A.: Plex: simplicial complexes in MATLAB (2000). http:\/\/mii.stanford.edu\/research\/comptop\/programs\/"},{"key":"71_CR44","unstructured":"Sexton, H., Vejdemo-Johansson, M.: jPlex (2008). http:\/\/www.math.colostate.edu\/~adams\/jplex\/index.html"},{"key":"71_CR45","unstructured":"Silva, V.d., Carlsson, G.: Topological estimation using witness complexes. In: Gross, M., Pfister, H., Alexa, M., Rusinkiewicz, S. (eds), SPBG\u201904 Symposium on Point\u2014Based Graphics 2004. The Eurographics Association (2004)"},{"issue":"1","key":"71_CR46","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1090\/S0002-9947-05-04079-1","volume":"358","author":"E Sk\u00f6ldberg","year":"2006","unstructured":"Sk\u00f6ldberg, E.: Morse theory from an algebraic viewpoint. Trans. Am. Math. Soc. 358(1), 115\u2013129 (2006)","journal-title":"Trans. Am. Math. Soc."},{"issue":"2","key":"71_CR47","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"RE Tarjan","year":"1979","unstructured":"Tarjan, R.E.: A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18(2), 110\u2013127 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"71_CR48","unstructured":"Tausz, A.: pHom: Persistent Homology in R (2011). https:\/\/cran.r-project.org\/src\/contrib\/Archive\/phom\/"},{"key":"71_CR49","unstructured":"Tausz, A., Vejdemo-Johansson, M., Adams, H.: JavaPlex: A research software package for persistent (co)homology. In: Hong, H., Yap, C. (eds), Proceedings of ICMS 2014, Lecture Notes in Computer Science 8592, pp. 129\u2013136 (2014). Software available at http:\/\/appliedtopology.github.io\/javaplex\/"},{"key":"71_CR50","unstructured":"The GUDHI Project. GUDHI User and Reference Manual. GUDHI Editorial Board, 2015. Software available at http:\/\/gudhi.gforge.inria.fr"},{"issue":"1","key":"71_CR51","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/BF01447877","volume":"97","author":"L Vietoris","year":"1927","unstructured":"Vietoris, L.: \u00dcber den h\u00f6heren Zusammenhang kompakter R\u00e4ume und eine Klasse von zusammenhangstreuen Abbildungen. Math. Ann. 97(1), 454\u2013472 (1927)","journal-title":"Math. Ann."},{"key":"71_CR52","doi-asserted-by":"crossref","unstructured":"Zhang, S., Xiao, M., Guo, C., Geng, L., Wang, H., Zhang, X.: Hypha: a framework based on separation of parallelisms to accelerate persistent homology matrix reduction. In: Proceedings of the ACM International Conference on Supercomputing, pp. 69\u201381 (2019). Software available at https:\/\/github.com\/simonzhang00\/hypha","DOI":"10.1145\/3330345.3332147"},{"key":"71_CR53","unstructured":"Zhang, S., Xiao, M., Wang, H.: GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes. In: Cabello, S., Chen, D.Z. (eds), 36th International Symposium on Computational Geometry (SoCG 2020), Volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 70:1\u201370:17. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2020). Software available at https:\/\/github.com\/simonzhang00\/ripser-plusplus.git"},{"issue":"2","key":"71_CR54","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00454-004-1146-y","volume":"33","author":"A Zomorodian","year":"2005","unstructured":"Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33(2), 249\u2013274 (2005)","journal-title":"Discrete Comput. Geom."}],"container-title":["Journal of Applied and Computational Topology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-021-00071-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41468-021-00071-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-021-00071-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T14:46:32Z","timestamp":1672497992000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41468-021-00071-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,17]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["71"],"URL":"https:\/\/doi.org\/10.1007\/s41468-021-00071-5","relation":{},"ISSN":["2367-1726","2367-1734"],"issn-type":[{"value":"2367-1726","type":"print"},{"value":"2367-1734","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,17]]},"assertion":[{"value":"11 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}