Computing the homology functor on semi-algebraic maps and diagrams

arXiv2207.10497MaRDI QIDQ6405642FDOQ6405642

Publication date: 21 July 2022

Abstract: Developing an algorithm for computing the Betti numbers of semi-algebraic sets with singly exponential complexity has been a holy grail in algorithmic semi-algebraic geometry and only partial results are known. In this paper we consider the more general problem of computing the image under the homology functor of a semi-algebraic map

f : X i g h t a r r o w Y

between closed and bounded semi-algebraic sets. For every fixed

e l l g e q 0

we give an algorithm with singly exponential complexity that computes bases of the homology groups

m a t h r m H_{i} (X), m a t h r m H_{i} (Y)

(with rational coefficients) and a matrix with respect to these bases of the induced linear maps

m a t h r m H_{i} (f) : m a t h r m H_{i} (X) i g h t a r r o w m a t h r m H_{i} (Y), 0 l e q i l e q e l l

. We generalize this algorithm to more general (zigzag) diagrams of maps between closed and bounded semi-algebraic sets and give a singly exponential algorithm for computing the homology functors on such diagrams. This allows us to give an algorithm with singly exponential complexity for computing barcodes of semi-algebraic zigzag persistent homology in small dimensions.

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Persistent homology and applications, topological data analysis (55N31) Classical real and complex (co)homology in algebraic geometry (14F25)

This page was built for publication: Computing the homology functor on semi-algebraic maps and diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405642)