Complexity and speed of semi-algebraic multi-persistence

2024/07/18 by Banerjee, Arindam, Basu, Saugata
#55N31 #Algebraic Topology (math.AT) #FOS: Mathematics #Primary 14F25 #Secondary 68W30

paper · doi:10.48550/arxiv.2407.13586

Abstract

Let R be a real closed field, S ⊂ Rⁿ a closed and bounded semi-algebraic set and f = (f₁,…,f_p):S → R^p a continuous semi-algebraic map. We study the poset module structure in homology induced by the simultaneous filtrations of S by the sub-level sets of the functions f_i from an algorithmic and quantitative point of view. For fixed dimensional homology we prove a singly exponential upper bound on the complexity of these modules which are encoded as certain semi-algebraically constructible functions on R^p × R^p. We also deduce for semi-algebraic filtrations of bounded complexity, upper bounds on the number of equivalence classes of finite poset modules that such a filtration induces -- establishing a tight analogy with a well-known graph theoretical result on the "speed'' of algebraically defined graphs.

Related

• Persistent homology of semi-algebraic sets
• Computing the homology functor on semi-algebraic maps and diagrams
• Fast Persistent Homology Computation for Functions on ℝ
• Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set
• Some Quantitative Results in Real Algebraic Geometry