Recognition: unknown
Computing Homomorphisms of Poset Representations with Applications to Multiparameter Persistence
Pith reviewed 2026-05-10 15:08 UTC · model grok-4.3
The pith
Uniqueness of lifts along free resolutions enables improved algorithms to compute homomorphism spaces between poset representations.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The main theoretical contribution is a uniqueness result for lifts of homomorphisms along free resolutions, which we use to obtain an algorithm running in O(n^4 (thick(Y) + thick(Omega^1 Y))^2 + T_ker(d,n)) time. We also apply and analyse a classical approach due to Green, Heath, and Struble, achieving O(n^3 thick(Y)^3 + n^4). Both improve on the naive O(n^6) bound when thick(Y) is small. Applied to the decomposition algorithm AIDA, the classical approach improves the asymptotic runtime the most.
What carries the argument
Uniqueness result for lifts of homomorphisms along free resolutions of finitely generated poset representations, which reduces Hom computation to solving a linear system after selecting one lift.
If this is right
- The classical approach most improves the asymptotic runtime of the AIDA decomposition algorithm for multiparameter persistence.
- Both new and classical algorithms improve on the naive O(n^6) bound whenever the maximal pointwise dimension is small.
- The classical method strengthens existing runtime results for uniquely graded modules.
- Practical implementations allow direct benchmarking against persistent homology computations on density-alpha bi-filtrations.
Where Pith is reading between the lines
- The observed practical speed of the lifting algorithm on 2-parameter modules indicates it may be the method of choice in applications even when its worst-case complexity is not the best.
- The general-poset formulation could support custom poset structures arising in data beyond the standard Z^d grid.
- The lift-uniqueness technique may adapt to compute related functors such as Ext groups in the same persistence setting.
Load-bearing premise
The representations are finitely generated and the uniqueness of lifts along free resolutions holds for the given poset.
What would settle it
A concrete counterexample of two distinct lifts of the same homomorphism along a free resolution for a finitely generated Z^d-representation would falsify the uniqueness claim and break the derived algorithm.
Figures
read the original abstract
We present algorithms to compute the vector space of homomorphisms Hom(X,Y) between finitely generated representations of the partially ordered set Z^d. Our results generalise to any partially ordered set. Our main theoretical contribution is a uniqueness result for lifts of homomorphisms along free resolutions, which we use to obtain an algorithm running in O(n^4 (thick(Y) + thick(Omega^1 Y))^2 + T_ker(d,n)) time, where thick(Y) denotes the maximal pointwise dimension of Y and T_ker is the time it takes to compute the kernel of a map between projective Z^d-modules. We also apply and analyse a classical approach due to Green, Heath, and Struble (J. Symbolic Comput., 2001), achieving O(n^3 thick(Y)^3 + n^4). Both improve on the naive O(n^6) bound when thick(Y) is small. Applied to the decomposition algorithm AIDA (Dey-J-Kerber, SoCG '25), the classical approach improves the asymptotic runtime the most, strengthening the result of Dey and Xin (J. Appl. Comput. Topology, 2022) for uniquely graded modules. We implement all algorithms in the Persistence Algebra C++ library and benchmark them on the persistent homology of density-alpha bi-filtrations of immune-cell locations. The classical approach has the best worst-case complexity, yet for 2-parameter modules, the lifting algorithm is fastest in practice.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents algorithms to compute the vector space Hom(X,Y) of homomorphisms between finitely generated representations of the poset Z^d (with generalization to arbitrary posets). The central theoretical contribution is a uniqueness result for lifts of homomorphisms along free resolutions, which yields an algorithm with complexity O(n^4 (thick(Y) + thick(Omega^1 Y))^2 + T_ker(d,n)). The authors also analyze and apply a classical method of Green-Heath-Struble achieving O(n^3 thick(Y)^3 + n^4), both improving on the naive O(n^6) bound for small thick(Y). These are applied to improve the runtime of the AIDA decomposition algorithm, implemented in the Persistence Algebra C++ library, and benchmarked on persistent homology of density-alpha bifiltrations from immune-cell data, where the lifting algorithm is fastest in practice for 2-parameter modules despite the classical method's superior worst-case complexity.
Significance. If the uniqueness result for lifts holds and the complexity analyses are correct, the work provides meaningful improvements to the computational toolkit for multiparameter persistence, a core task in topological data analysis. The explicit application to strengthening the AIDA algorithm and the independent implementation with external benchmarks on real data are strengths that increase the practical impact. The generalization to arbitrary posets further broadens potential use cases.
minor comments (3)
- The abstract introduces the notation thick(Y) and thick(Omega^1 Y) without a brief inline definition or pointer to the preliminaries; adding this would improve immediate readability for readers outside the subfield.
- The complexity expression includes T_ker(d,n) (time to compute kernels of maps between projective Z^d-modules); a short sentence clarifying its dependence on d and n in the introduction would help contextualize the bound.
- Section 4 (or wherever the uniqueness theorem is stated) would benefit from an explicit statement of the precise hypotheses on the poset and the finite-generation assumption to make the scope of the lift-uniqueness result immediately clear.
Simulated Author's Rebuttal
We thank the referee for their positive and accurate summary of our manuscript, as well as for recommending minor revision. We appreciate the recognition of the theoretical contribution, the complexity improvements, the strengthening of the AIDA algorithm, the implementation, and the benchmarks on real data.
Circularity Check
No significant circularity; derivation is self-contained
full rationale
The paper presents a new uniqueness result for lifts of homomorphisms along free resolutions of finitely generated poset representations as its main theoretical contribution, which is then used to derive the stated algorithm and complexity bound. This result is not imported via self-citation but claimed and (presumably) proven within the manuscript. The classical Green-Heath-Struble method is cited from an external 2001 reference and analyzed separately with its own complexity. Application to the AIDA algorithm is an extension rather than a load-bearing premise for the core claims. Implementation in an open library and benchmarking on external immune-cell data provide independent verification outside any fitted parameters or self-generated inputs. No self-definitional equations, fitted inputs renamed as predictions, or ansatzes smuggled through citations appear in the derivation chain.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Representations of the poset Z^d (or general posets) are finitely generated modules over the associated ring
- domain assumption Free resolutions exist and lifts of homomorphisms along them satisfy the claimed uniqueness property
Reference graph
Works this paper leans on
-
[1]
Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets
Ángel Javier Alonso and Michael Kerber. “Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets”. In:International Symposium on Computational Geometry (SoCG). 2023.doi:10.4230/LIPICS.SOCG.2023.7
-
[2]
Probabilistic Analysis of Multiparam- eter Persistence Decompositions into Intervals
Ángel Javier Alonso, Michael Kerber, and Primoz Skraba. “Probabilistic Analysis of Multiparam- eter Persistence Decompositions into Intervals”. In:International Symposium on Computational Geometry (SoCG). 2024.doi:10.4230/LIPIcs.SoCG.2024.6
-
[3]
Relative Koszul coresolutions and relative Betti numbers
Hideto Asashiba. “Relative Koszul coresolutions and relative Betti numbers”. In:Journal of Pure and Applied Algebra229.3 (2025), p. 107905.issn: 0022-4049.doi:https://doi.org/10. 1016/j.jpaa.2025.107905.url: https://www.sciencedirect.com/science/article/pii/ S0022404925000441
-
[4]
Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls.Fast free resolutions of bifiltered chain complexes. 2026. arXiv:2512 . 08652 [math.AT].url: https : //arxiv.org/abs/2512.08652
-
[5]
Efficient Two-Parameter Persistence Compu- tation via Cohomology
Ulrich Bauer, Fabian Lenzen, and Michael Lesnick. “Efficient Two-Parameter Persistence Compu- tation via Cohomology”. In:39th International Symposium on Computational Geometry (SoCG 2023). Ed. by Erin W. Chambers and Joachim Gudmundsson. Vol. 258. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zent...
-
[6]
20023.url:https://github.com/MBender/muphasa
Matías Bender, Oliver Gäfvert, and Michael Lesnick.Computing minimal presentations of multi-parameter persistent homology. 20023.url:https://github.com/MBender/muphasa
-
[8]
Stability of 2-Parameter Persistent Homology
Andrew J. Blumberg and Michael Lesnick. “Stability of 2-Parameter Persistent Homology”. In: Foundations of Computational Mathematics24.2 (2024), pp. 385–427.doi:10.1007/S10208- 022-09576-6
-
[9]
Topological consistency via kernel estimation
Omer Bobrowski, Sayan Mukherjee, and Jonathan E. Taylor. “Topological consistency via kernel estimation”. In:Bernoulli23.1 (2017), pp. 288–328.issn: 13507265.url:http://www.jstor. org/stable/44075471(visited on 08/28/2025)
-
[10]
The Magma algebra system. I. The user language
Wieb Bosma, John Cannon, and Catherine Playoust. “The Magma algebra system. I. The user language”. In:Journal of Symbolic Computation24.3-4 (1997), pp. 235–265.doi:10.1006/jsco. 1996.0125. 3https://github.com/JanJend/Stable-Decomposition 22
-
[11]
Jürgen Herzog.Cohen-Macaulay Rings
Winfried Bruns and H. Jürgen Herzog.Cohen-Macaulay Rings. 2nd ed. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1998
1998
-
[12]
Gunnar Carlsson and Vin de Silva. “Zigzag Persistence”. In:Foundations of Computational Mathematics10.4 (2010), pp. 367–405.issn: 1615-3383.doi: 10.1007/s10208-010-9066-0 . url:https://doi.org/10.1007/s10208-010-9066-0
-
[13]
The Theory of Multidimensional Persistence
Gunnar Carlsson and Afra Zomorodian. “The Theory of Multidimensional Persistence”. In: Discrete and Computational Geometry42 (June 2007), pp. 71–93.doi:10.1007/s00454-009- 9176-0
-
[14]
Polynomial time algorithms for modulesoverfinitedimensionalalgebras
Alexander Chistov, Gábor Ivanyos, and Marek Karpinski. “Polynomial time algorithms for modulesoverfinitedimensionalalgebras”.In:International Symposium on Symbolic and Algebraic Computation (ISSAC). 1997.doi:10.1145/258726.258751
-
[16]
Dey, Jan Jendrysiak, and Michael Kerber.Decomposing Multiparameter Persistence Modules
Tamal K. Dey, Jan Jendrysiak, and Michael Kerber.Decomposing Multiparameter Persistence Modules. 2025. arXiv:2504.08119 [math.RT].url:https://arxiv.org/abs/2504.08119
-
[17]
Decomposing Multiparameter Persistence Modules
Tamal K. Dey, Jan Jendrysiak, and Michael Kerber. “Decomposing Multiparameter Persistence Modules”. In:41st International Symposium on Computational Geometry (SoCG 2025). Ed. by Oswin Aichholzer and Haitao Wang. Vol. 332. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, ...
-
[18]
Tamal K. Dey and Shreyas N. Samaga.Quasi Zigzag Persistence: A Topological Framework for Analyzing Time-Varying Data. 2026. arXiv:2502.16049 [cs.LG].url: https://arxiv.org/ abs/2502.16049
-
[19]
Computing Bottleneck Distance for 2-D Interval Decomposable Modules
Tamal K. Dey and Cheng Xin. “Computing Bottleneck Distance for 2-D Interval Decomposable Modules”. In:International Symposium on Computational Geometry (SoCG). 2018.doi:10. 4230/LIPIcs.SoCG.2018.32
2018
-
[20]
Generalized Persistence Algorithm for Decomposing Multipa- rameter Persistence Modules
Tamal K. Dey and Cheng Xin. “Generalized Persistence Algorithm for Decomposing Multipa- rameter Persistence Modules”. In:Journal of Applied and Computational Topology6 (2022), pp. 271–322.doi:10.1007/s41468-022-00087-5
-
[21]
Topological Persistence and Simplification
Edelsbrunner, Letscher, and Zomorodian. “Topological Persistence and Simplification”. In: Discrete Comput. Geom.28.4 (Nov. 2002), 511–533.issn: 0179-5376.doi:10.1007/s00454- 002-2885-2.url:https://doi.org/10.1007/s00454-002-2885-2
-
[22]
The Multi-cover Persistence of Euclidean Balls
Herbert Edelsbrunner and Georg Osang. “The Multi-cover Persistence of Euclidean Balls”. In:34th International Symposium on Computational Geometry (SoCG 2018). Ed. by Bettina Speckmann and Csaba D. Tóth. Vol. 99. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018, 34:1– 34:1...
-
[23]
Refined algo- rithms to compute syzygies
Burçin Eröcal, Oleksandr Motsak, Frank-Olaf Schreyer, and Andreas Steenpaß. “Refined algo- rithms to compute syzygies”. In:Journal of Symbolic Computation74 (2016), pp. 308–327.issn: 0747-7171.doi:https://doi.org/10.1016/j.jsc.2015.07.004
- [24]
-
[25]
The GAP Group
GAP – Groups, Algorithms, and Programming, Version 4.13.1. The GAP Group. 2024.url: https://www.gap-system.org
2024
-
[26]
On Graded Rings, II (Zn-graded rings)
Shiro Goto and Keiichi Watanabe. “On Graded Rings, II (Zn-graded rings)”. In:Tokyo Journal of Mathematics1 (1978).doi:10.3836/tjm/1270216496. 23
-
[27]
Constructing Homomorphism Spaces and Endomorphism Rings
Edward L. Green, Lenwood S. Heath, and Craig A. Struble. “Constructing Homomorphism Spaces and Endomorphism Rings”. In:Journal of Symbolic Computation32.1 (2001), pp. 101– 117.issn: 0747-7171.doi: https : / / doi . org / 10 . 1006 / jsco . 2001 . 0454.url: https : //www.sciencedirect.com/science/article/pii/S0747717101904547
2001
-
[28]
Delaunay Bifiltrations of Functions on Point Clouds
Ángel Javier Alonso, Michael Kerber, Tung Lam, and Michael Lesnick. “Delaunay Bifiltrations of Functions on Point Clouds”. In:Symposium on Discrete Algorithms (SODA). 2024.doi: 10.1137/1.9781611977912.173
-
[29]
(1971).Some Limit Theorems in Statistics.SIAM, Philadelphia
Michael Kerber and Alexander Rolle. “Fast Minimal Presentations of Bi-graded Persistence Modules”. In:Algorithm Engineering and Experiments (ALENEX). 2021.doi:10.1137/1. 9781611976472.16
work page doi:10.1137/1 2021
-
[30]
Partially ordered sets of finite type
Mark Kleiner. “Partially ordered sets of finite type”. In:Journal of Soviet Mathematics3.5 (1975), pp. 607–615.issn: 1573-8795.doi:10.1007/BF01084663.url: https://doi.org/10. 1007/BF01084663
-
[31]
Computational methods for multi-parameter persistence
Fabian Lenzen. “Computational methods for multi-parameter persistence”. en. PhD thesis. Technische Universität München, 2023, p. 156.url:https://mediatum.ub.tum.de/1713777
-
[32]
Fabian Lenzen.Computing Flat-Injective Presentations of Multiparameter Persistence Modules
- [33]
-
[34]
Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology
Michael Lesnick and Matthew Wright. “Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology”. In:SIAM Journal on Applied Algebra and Geometry6.2 (2022), pp. 267–298.doi:10.1137/20M1388425
- [35]
-
[36]
Indecomposable representations of finite ordered sets
Michèle Loupias. “Indecomposable representations of finite ordered sets”. In:Representations of Algebras. Springer, 1975, pp. 201–209
1975
-
[37]
Computing Decompositions of Modules over Finite- Dimensional Algebras
Klaus M. Lux and Magdolna Szőke. “Computing Decompositions of Modules over Finite- Dimensional Algebras”. In:Experimental Mathematics16.1 (2007), pp. 1–6
2007
-
[38]
Computing homomorphism spaces between modules over finite dimensional algebras
Klaus M. Lux and Magdolna Szőke. “Computing homomorphism spaces between modules over finite dimensional algebras.” eng. In:Experimental Mathematics12.1 (2003), pp. 91–98.url: http://eudml.org/doc/50968
2003
-
[39]
Classics in Mathematics
Saunders MacLane.Homology. Classics in Mathematics. Springer, 2012.isbn: 9783642620294. url:https://books.google.at/books?id=ujRqCQAAQBAJ
2012
-
[40]
Graded Greenlees–May Duality and the Čech Hull
Ezra Miller. “Graded Greenlees–May Duality and the Čech Hull”. In:Local Cohomology and Its Applications. Vol. 226. Lecture Notes in Pure and Applied Mathematics. Marcel Dekker, 2001, pp. 233–253
2001
-
[41]
The Alexander Duality Functors and Local Duality with Monomial Support
Ezra Miller. “The Alexander Duality Functors and Local Duality with Monomial Support”. In:Journal of Algebra231.1 (2000), pp. 180–234.issn: 0021-8693.doi: https://doi.org/ 10.1006/jabr.2000.8359.url: https://www.sciencedirect.com/science/article/pii/ S0021869300983595
-
[42]
Ezra Miller and Bernd Sturmfels.Combinatorial Commutative Algebra. 1st ed. Graduate Texts in Mathematics. New York, NY: Springer, 2005, pp. XIV, 420.isbn: 978-0-387-23707-7.doi: 10.1007/b138602
-
[43]
Representations of partially ordered sets
L. A. Nazarova and A. V. Roiter. “Representations of partially ordered sets”. In:Journal of Soviet Mathematics3.5 (1975), pp. 585–606.issn: 1573-8795.doi:10.1007/BF01084662.url: https://doi.org/10.1007/BF01084662
-
[44]
2011.doi:10.1007/978-0-85729-177-6
Irena Peeva.Graded Syzygies. 2011.doi:10.1007/978-0-85729-177-6
-
[45]
Matrix problems and representations of Bocs’s
A. V. Rojter. “Matrix problems and representations of Bocs’s”. In:Representation Theory I: Proceedings of the Workshop on the Present Trends in Representation Theory, Ottawa, Carleton University, August 13 – 18, 1979. Ed. by Vlastimil Dlab and Peter Gabriel. Berlin, Heidelberg: Springer Berlin Heidelberg, 1980, pp. 288–324.isbn: 978-3-540-38385-7.doi:10. ...
-
[46]
A Multicover Nerve for Geometric Inference
Donald R. Sheehy. “A Multicover Nerve for Geometric Inference”. In:CCCG: Canadian Confer- ence in Computational Geometry. 2012, pp. 309–314. 24
2012
-
[47]
Multiparameter persistent homology landscapes identify immune cell spatial patterns in tumors
Oliver Vipond, Joshua A Bull, Philip S Macklin, Ulrike Tillmann, Christopher W Pugh, Helen M Byrne, and Heather A Harrington. “Multiparameter persistent homology landscapes identify immune cell spatial patterns in tumors”. en. In:Proc Natl Acad Sci U S A118.41 (Oct. 2021). A Algorithms Algorithm 5:Computation of Local Cokernels Input:A presentationN∈kG×Ro...
2021
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.