Computing the homology of real projective sets
From MaRDI portal
Publication:667646
DOI10.1007/S10208-017-9358-8zbMATH Open1506.55014OpenAlexW2962955948MaRDI QIDQ667646FDOQ667646
Abstract: We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of real projective varieties. Here numerical means that the algorithm is numerically stable (in a sense to be made precise). Its cost depends on the condition of the input as well as on its size and is singly exponential in the number of variables (the dimension of the ambient space) and polynomial in the condition and the degrees of the defining polynomials. In addition, we show that outside of an exceptional set of measure exponentially small in the size of the data, the algorithm takes exponential time.
Recommendations
- Computing the homology of semialgebraic sets. II: General formulas
- Numerical homotopies to compute generic points on positive dimensional algebraic sets
- Computing the homology of basic semialgebraic sets in weak exponential time
- Computing the homology of semialgebraic sets. I: Lax formulas
- scientific article; zbMATH DE number 2151222
Cites work
- scientific article; zbMATH DE number 421657 (Why is no real title available?)
- scientific article; zbMATH DE number 47206 (Why is no real title available?)
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- scientific article; zbMATH DE number 3564960 (Why is no real title available?)
- scientific article; zbMATH DE number 1254302 (Why is no real title available?)
- scientific article; zbMATH DE number 3992817 (Why is no real title available?)
- scientific article; zbMATH DE number 863503 (Why is no real title available?)
- A numerical algorithm for zero counting. I: Complexity and accuracy
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- A numerical algorithm for zero counting. III: Randomization and condition
- A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
- Approximate zeros and condition numbers
- Average-case complexity without the black swans
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties
- Complexity estimates depending on condition and round-off error
- Complexity of Bezout's Theorem I: Geometric Aspects
- Complexity of Bezout's theorem. III: Condition number and packing
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Complexity theory of numerical linear algebra
- Computational topology. An introduction
- Computing the first Betti number of a semi-algebraic set
- Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time
- Condition. The geometry of numerical algorithms
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Exotic quantifiers, complexity classes, and complete problems
- Finding the homology of submanifolds with high confidence from random samples
- Heights of varieties in multiprojective spaces and arithmetic nullstellensätze
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Linear programming, complexity theory and elementary functional analysis
- Numerical instability of resultant methods for multidimensional rootfinding
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the volume of tubular neighborhoods of real algebraic varieties
- Smoothed analysis of some condition numbers
- Solving linear programs with finite precision. II: Algorithms
- Some perturbation theory for linear programming
- The Probability That a Numerical Analysis Problem is Difficult
Cited in
(12)- Computing the homology of basic semialgebraic sets in weak exponential time
- Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
- Computing the homology of semialgebraic sets. II: General formulas
- Sampling and homology via bottlenecks
- Computing the homology of semialgebraic sets. I: Lax formulas
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- Effective homology and periods of complex projective hypersurfaces
- On the complexity of the Plantinga-Vegter algorithm
- Low-degree approximation of random polynomials
- Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties
- Condition numbers for the cube. I: Univariate polynomials and hypersurfaces
- Smoothed analysis for the condition number of structured real polynomial systems
This page was built for publication: Computing the homology of real projective sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q667646)
