Computing the Homology Functor on Semi-algebraic Maps and Diagrams.
Saved in:
| Title: | Computing the Homology Functor on Semi-algebraic Maps and Diagrams. |
|---|---|
| Authors: | Basu, Saugata1 (AUTHOR) sbasu@math.purdue.edu, Karisani, Negin2 (AUTHOR) |
| Source: | Discrete & Computational Geometry. Dec2024, Vol. 72 Issue 4, p1437-1462. 26p. |
| Subjects: | Semialgebraic sets, Linear operators, Bar codes, Algorithms, Geometry |
| 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 continuous semi-algebraic map f : X → Y between closed and bounded semi-algebraic sets. For every fixed ℓ ≥ 0 we give an algorithm with singly exponential complexity that computes bases of the homology groups H i (X) , H i (Y) (with rational coefficients) and a matrix with respect to these bases of the induced linear maps H i (f) : H i (X) → H i (Y) , 0 ≤ i ≤ ℓ . We generalize this algorithm to more general (zigzag) diagrams of continuous semi-algebraic 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| 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 continuous semi-algebraic map f : X → Y between closed and bounded semi-algebraic sets. For every fixed ℓ ≥ 0 we give an algorithm with singly exponential complexity that computes bases of the homology groups H i (X) , H i (Y) (with rational coefficients) and a matrix with respect to these bases of the induced linear maps H i (f) : H i (X) → H i (Y) , 0 ≤ i ≤ ℓ . We generalize this algorithm to more general (zigzag) diagrams of continuous semi-algebraic 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. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 01795376 |
| DOI: | 10.1007/s00454-024-00627-z |
