{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T17:12:05Z","timestamp":1768410725647,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T00:00:00Z","timestamp":1696636800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T00:00:00Z","timestamp":1696636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2049010"],"award-info":[{"award-number":["CCF-2049010"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740761"],"award-info":[{"award-number":["CCF-1740761"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1547357"],"award-info":[{"award-number":["DMS-1547357"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1901360"],"award-info":[{"award-number":["IIS-1901360"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The notion of generalized rank in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. However, its efficient computation has not yet been studied in the literature. We show that the generalized rank over a finite interval <jats:italic>I<\/jats:italic> of a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textbf{Z}^2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>Z<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-indexed persistence module <jats:italic>M<\/jats:italic> is equal to the generalized rank of the zigzag module that is induced on a certain path in <jats:italic>I<\/jats:italic> tracing mostly its boundary. Hence, we can compute the generalized rank of <jats:italic>M<\/jats:italic> over <jats:italic>I<\/jats:italic> by computing the barcode of the zigzag module obtained by restricting to that path. If <jats:italic>M<\/jats:italic> is the homology of a bifiltration <jats:italic>F<\/jats:italic> of <jats:inline-formula><jats:alternatives><jats:tex-math>$$t$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>t<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> simplices (while accounting for multi-criticality) and <jats:italic>I<\/jats:italic> consists of <jats:inline-formula><jats:alternatives><jats:tex-math>$$t$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>t<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> points, this computation takes <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(t^\\omega )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>t<\/mml:mi>\n                      <mml:mi>\u03c9<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time where <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega \\in [2,2.373)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c9<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>2.373<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the exponent of matrix multiplication. We apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module <jats:italic>M<\/jats:italic>, determine whether <jats:italic>M<\/jats:italic> is interval decomposable and, if so, compute all intervals supporting its indecomposable summands.<\/jats:p>","DOI":"10.1007\/s00454-023-00584-z","type":"journal-article","created":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T18:01:47Z","timestamp":1696701707000},"page":"67-94","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications"],"prefix":"10.1007","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5160-9738","authenticated-orcid":false,"given":"Tamal K.","family":"Dey","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8081-5872","authenticated-orcid":false,"given":"Woojin","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Facundo","family":"M\u00e9moli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,7]]},"reference":[{"key":"584_CR1","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF01298413","volume":"6","author":"P Gabriel","year":"1972","unstructured":"Gabriel, P.: Unzerlegbare darstellungen i. Manuscr. Math. 6, 71\u2013103 (1972)","journal-title":"Manuscr. Math."},{"issue":"05","key":"584_CR2","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(05), 1550066 (2015)","journal-title":"J. Algebra Appl."},{"key":"584_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/9781009099950","volume-title":"Computational Topology for Data Analysis","author":"TK Dey","year":"2022","unstructured":"Dey, T.K., Wang, Y.: Computational Topology for Data Analysis. Cambridge University Press, Cambridge, UK (2022)"},{"key":"584_CR4","volume-title":"Computational Topology: An Introduction","author":"H Edelsbrunner","year":"2010","unstructured":"Edelsbrunner, H., Harer, J.: Computational Topology: An Introduction. American Mathematical Society, Providence, RI (2010)"},{"key":"584_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2020.107171","volume":"369","author":"U Bauer","year":"2020","unstructured":"Bauer, U., Botnan, M.B., Oppermann, S., Steen, J.: Cotorsion torsion triples and the representation theory of filtered hierarchical clustering. Adva. Math. 369, 107171 (2020)","journal-title":"Adva. Math."},{"issue":"4","key":"584_CR6","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10208-010-9066-0","volume":"10","author":"G Carlsson","year":"2010","unstructured":"Carlsson, G., de Silva, V.: Zigzag persistence. Found. Comput. Math. 10(4), 367\u2013405 (2010)","journal-title":"Found. Comput. Math."},{"key":"584_CR7","doi-asserted-by":"crossref","unstructured":"Carlsson, G., M\u00e9moli, F.: Multiparameter hierarchical clustering methods. In: Classification as a Tool for Research, pp. 63\u201370. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-10745-0_6"},{"issue":"1","key":"584_CR8","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s00454-009-9176-0","volume":"42","author":"G Carlsson","year":"2009","unstructured":"Carlsson, G., Zomorodian, A.: The theory of multidimensional persistence. Discrete Comput. Geom. 42(1), 71\u201393 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"584_CR9","unstructured":"Dey, T.K., Hou, T.: Updating zigzag persistence and maintaining representatives over changing filtrations. CoRR arxiv:2112.02352 (2021)"},{"issue":"1","key":"584_CR10","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/s00454-015-9746-2","volume":"55","author":"EG Escolar","year":"2016","unstructured":"Escolar, E.G., Hiraoka, Y.: Persistence modules on commutative ladders of finite type. Discrete Comput. Geom. 55(1), 100\u2013157 (2016)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"584_CR11","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1007\/s00454-019-00168-w","volume":"66","author":"W Kim","year":"2021","unstructured":"Kim, W., M\u00e9moli, F.: Spatiotemporal persistent homology for dynamic metric spaces. Discrete Comput. Geom. 66(3), 831\u2013875 (2021)","journal-title":"Discrete Comput. Geom."},{"key":"584_CR12","unstructured":"Lesnick, M.: Multidimensional interleavings and applications to topological inference. PhD thesis, Stanford University (2012)"},{"issue":"3","key":"584_CR13","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s10208-015-9255-y","volume":"15","author":"M Lesnick","year":"2015","unstructured":"Lesnick, M.: The theory of the interleaving distance on multidimensional persistence modules. Found. Comput. Math. 15(3), 613\u2013650 (2015)","journal-title":"Found. Comput. Math."},{"key":"584_CR14","unstructured":"Miller, E.: Modules over posets: commutative and homological algebra. arXiv preprint arXiv:1908.09750 (2019)"},{"issue":"2","key":"584_CR15","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10851-008-0096-z","volume":"32","author":"S Biasotti","year":"2008","unstructured":"Biasotti, S., Cerri, A., Frosini, P., Giorgi, D., Landi, C.: Multidimensional size functions for shape comparison. J. Math. Imaging Vis. 32(2), 161\u2013179 (2008)","journal-title":"J. Math. Imaging Vis."},{"key":"584_CR16","unstructured":"Lesnick, M., Wright, M.: Interactive visualization of 2-d persistence modules. arXiv preprint arXiv:1512.00180 (2015)"},{"issue":"3","key":"584_CR17","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1137\/20M1353605","volume":"5","author":"C Cai","year":"2021","unstructured":"Cai, C., Kim, W., M\u00e9moli, F., Wang, Y.: Elder-rule-staircodes for augmented metric spaces. SIAM J. Appl. Algebra Geom. 5(3), 417\u2013454 (2021)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"584_CR18","doi-asserted-by":"publisher","unstructured":"Botnan, M., Lebovici, V., Oudot, S.: On Rectangle-Decomposable 2-Parameter Persistence Modules. In: 36th International Symposium on Computational Geometry (SoCG 2020), vol. 164 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2020.22","DOI":"10.4230\/LIPIcs.SoCG.2020.22"},{"issue":"2","key":"584_CR19","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s00454-019-00165-z","volume":"63","author":"J Cochoy","year":"2020","unstructured":"Cochoy, J., Oudot, S.: Decomposition of exact pfd persistence bimodules. Discrete Comput. Geom. 63(2), 255\u2013293 (2020)","journal-title":"Discrete Comput. Geom."},{"key":"584_CR20","unstructured":"Asashiba, H., Escolar, E.G., Nakashima, K., Yoshiwaki, M.: On approximation of $$2d$$-persistence modules by interval-decomposables. arXiv preprint arXiv:1911.01637 (2019)"},{"key":"584_CR21","unstructured":"Clause, N., Kim, W., Memoli, F.: The discriminating power of the generalized rank invariant. arXiv preprint arXiv:2207.11591 (2022)"},{"issue":"4","key":"584_CR22","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s41468-021-00075-1","volume":"5","author":"W Kim","year":"2021","unstructured":"Kim, W., M\u00e9moli, F.: Generalized persistence diagrams for persistence modules over posets. J. Appl. Comput. Topol. 5(4), 533\u2013581 (2021)","journal-title":"J. Appl. Comput. Topol."},{"issue":"3","key":"584_CR23","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s41468-018-0012-6","volume":"1","author":"A Patel","year":"2018","unstructured":"Patel, A.: Generalized persistence diagrams. J. Appl. Comput. Topol. 1(3), 397\u2013419 (2018)","journal-title":"J. Appl. Comput. Topol."},{"key":"584_CR24","unstructured":"Kim, W., M\u00e9moli, F.: Rank invariant for zigzag modules. arXiv preprint arXiv:1810.11517v1 (2018)"},{"key":"584_CR25","doi-asserted-by":"crossref","unstructured":"Chambers, E., Letscher, D.: Persistent homology over directed acyclic graphs. In: Research in Computational Topology, pp. 11\u201332. Springer, (2018)","DOI":"10.1007\/978-3-319-89593-2_2"},{"key":"584_CR26","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2022.101879","volume":"105","author":"H Asashiba","year":"2022","unstructured":"Asashiba, H., Buchet, M., Escolar, E.G., Nakashima, K., Yoshiwaki, M.: On interval decomposability of 2d persistence modules. Comput. Geom. 105, 101879 (2022)","journal-title":"Comput. Geom."},{"key":"584_CR27","first-page":"1","volume":"9","author":"TK Dey","year":"2022","unstructured":"Dey, T.K., Xin, C.: Generalized persistence algorithm for decomposing multiparameter persistence modules. J. Appl. Comput. Topol. 9, 1\u201352 (2022)","journal-title":"J. Appl. Comput. Topol."},{"key":"584_CR28","unstructured":"Kerber, M.: Multi-parameter persistent homology is practical. In: NeurIPS 2020 Workshop on Topological Data Analysis and Beyond (2020)"},{"key":"584_CR29","first-page":"1","volume":"8","author":"L Betthauser","year":"2021","unstructured":"Betthauser, L., Bubenik, P., Edwards, P.B.: Graded persistence diagrams and persistence landscapes. Discrete Comput. Geom. 8, 1\u201328 (2021)","journal-title":"Discrete Comput. Geom."},{"key":"584_CR30","unstructured":"Botnan, M., Oppermann, S., Oudot, S.: Signed barcodes for multi-parameter persistence via rank decompositions and rank-exact resolutions. arXiv preprint arXiv:2107.06800 (2021)"},{"key":"584_CR31","unstructured":"Bubenik, P., Elchesen, A.: Virtual persistence diagrams, signed measures, and wasserstein distance. arXiv preprint arXiv:2012.10514 (2020)"},{"key":"584_CR32","unstructured":"Kim, W., Moore, S.: Bigraded betti numbers and generalized persistence diagrams. arXiv preprint arXiv:2111.02551v3 (2021)"},{"key":"584_CR33","unstructured":"McCleary, A., Patel, A.: Edit distance and persistence diagrams over lattices. arXiv preprint arXiv:2010.07337 (2020)"},{"issue":"6","key":"584_CR34","doi-asserted-by":"publisher","first-page":"3133","DOI":"10.2140\/agt.2018.18.3133","volume":"18","author":"M Botnan","year":"2018","unstructured":"Botnan, M., Lesnick, M.: Algebraic stability of zigzag persistence modules. Algebraic Geometric Topol. 18(6), 3133\u20133204 (2018)","journal-title":"Algebraic Geometric Topol."},{"key":"584_CR35","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1017\/S002776300002290X","volume":"1","author":"G Azumaya","year":"1950","unstructured":"Azumaya, G.: Corrections and supplementaries to my paper concerning Krull\u2013Remak\u2013Schmidt\u2019s theorem. Nagoya Math. J. 1, 117\u2013124 (1950)","journal-title":"Nagoya Math. J."},{"issue":"4","key":"584_CR36","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/BF00531932","volume":"2","author":"GC Rota","year":"1964","unstructured":"Rota, G.C.: On the foundations of combinatorial theory i. theory of M\u00f6bius functions. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte Gebiete 2(4), 340\u2013368 (1964)","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte Gebiete"},{"key":"584_CR37","series-title":"Cambridge Studies in Advanced Mathematics","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139058520","volume-title":"Enumerative Combinatorics","author":"RP Stanley","year":"2011","unstructured":"Stanley, R.P.: Enumerative Combinatorics. Cambridge Studies in Advanced Mathematics, vol. 1, 2nd edn. Cambridge University Press, Cambridge (2011)","edition":"2"},{"key":"584_CR38","volume-title":"Categories for the Working Mathematician","author":"S Mac Lane","year":"2013","unstructured":"Mac Lane, S.: Categories for the Working Mathematician, vol. 5. Springer, New York (2013)"},{"key":"584_CR39","doi-asserted-by":"crossref","unstructured":"Milosavljevi\u0107, N., Morozov, D., Skraba, P.: Zigzag persistent homology in matrix multiplication time. In: Proceedings of the Twenty-seventh Annual Symposium on Computational Geometry, pp. 216\u2013225 (2011)","DOI":"10.1145\/1998196.1998229"},{"key":"584_CR40","doi-asserted-by":"publisher","unstructured":"Dey, T.K., Hou, T.: Fast computation of zigzag persistence. In: 30th Annual European Symposium on Algorithms, ESA 2022. LIPIcs, vol. 244 (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2022.43","DOI":"10.4230\/LIPIcs.ESA.2022.43"},{"key":"584_CR41","unstructured":"Xin, C., Mukherjee, S., Samaga, S., Dey, T.K.: GRIL: a 2-parameter persistence based vectorization for machine learning. CoRR arXiv:2304.04970 (2023)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00584-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00584-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00584-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,6]],"date-time":"2024-01-06T20:02:29Z","timestamp":1704571349000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00584-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,7]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["584"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00584-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,7]]},"assertion":[{"value":"14 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}