Efficient Computation of a Semi-Algebraic Basis of the First Homology Group of a Semi-Algebraic Set.
Saved in:
| Title: | Efficient Computation of a Semi-Algebraic Basis of the First Homology Group of a Semi-Algebraic Set. |
|---|---|
| Authors: | Basu, Saugata1 (AUTHOR) sbasu@math.purdue.edu, Percival, Sarah2 (AUTHOR) |
| Source: | Discrete & Computational Geometry. Sep2024, Vol. 72 Issue 2, p622-664. 43p. |
| Subjects: | Semialgebraic sets, Algebraic fields, Algebraic geometry, Point set theory, Algorithms |
| Abstract: | Let R be a real closed field and C the algebraic closure of R . We give an algorithm for computing a semi-algebraic basis for the first homology group, H 1 (S , F) , with coefficients in a field F , of any given semi-algebraic set S ⊂ R k defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves s polynomials whose degrees are bounded by d, the complexity of the algorithm is bounded by (s d) k O (1) . This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zeroth homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset Γ of the given semi-algebraic set S, such that H q (S , Γ) = 0 for q = 0 , 1 . We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety X of dimension n, there exists Zariski closed subsets Z (n - 1) ⊃ ⋯ ⊃ Z (1) ⊃ Z (0) with dim C Z (i) ≤ i , and H q (X , Z (i)) = 0 for 0 ≤ q ≤ i . We conjecture a quantitative version of this result in the semi-algebraic category, with X and Z (i) replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of Z (0) and Z (1) with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing Z (0) ). [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: | Let R be a real closed field and C the algebraic closure of R . We give an algorithm for computing a semi-algebraic basis for the first homology group, H 1 (S , F) , with coefficients in a field F , of any given semi-algebraic set S ⊂ R k defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves s polynomials whose degrees are bounded by d, the complexity of the algorithm is bounded by (s d) k O (1) . This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zeroth homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset Γ of the given semi-algebraic set S, such that H q (S , Γ) = 0 for q = 0 , 1 . We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety X of dimension n, there exists Zariski closed subsets Z (n - 1) ⊃ ⋯ ⊃ Z (1) ⊃ Z (0) with dim C Z (i) ≤ i , and H q (X , Z (i)) = 0 for 0 ≤ q ≤ i . We conjecture a quantitative version of this result in the semi-algebraic category, with X and Z (i) replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of Z (0) and Z (1) with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing Z (0) ). [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 01795376 |
| DOI: | 10.1007/s00454-024-00626-0 |
