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.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 179949824 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Efficient Computation of a Semi-Algebraic Basis of the First Homology Group of a Semi-Algebraic Set. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Basu%2C+Saugata%22">Basu, Saugata</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> sbasu@math.purdue.edu</i><br /><searchLink fieldCode="AR" term="%22Percival%2C+Sarah%22">Percival, Sarah</searchLink><relatesTo>2</relatesTo> (AUTHOR) – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Sep2024, Vol. 72 Issue 2, p622-664. 43p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Semialgebraic+sets%22">Semialgebraic sets</searchLink><br /><searchLink fieldCode="DE" term="%22Algebraic+fields%22">Algebraic fields</searchLink><br /><searchLink fieldCode="DE" term="%22Algebraic+geometry%22">Algebraic geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Point+set+theory%22">Point set theory</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=179949824 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00454-024-00626-0 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 43 StartPage: 622 Subjects: – SubjectFull: Semialgebraic sets Type: general – SubjectFull: Algebraic fields Type: general – SubjectFull: Algebraic geometry Type: general – SubjectFull: Point set theory Type: general – SubjectFull: Algorithms Type: general Titles: – TitleFull: Efficient Computation of a Semi-Algebraic Basis of the First Homology Group of a Semi-Algebraic Set. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Basu, Saugata – PersonEntity: Name: NameFull: Percival, Sarah IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: Sep2024 Type: published Y: 2024 Identifiers: – Type: issn-print Value: 01795376 Numbering: – Type: volume Value: 72 – Type: issue Value: 2 Titles: – TitleFull: Discrete & Computational Geometry Type: main |
| ResultId | 1 |
