Computing the Homology of Real Projective Sets
Preprint
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.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Castelnuovo–Mumford Regularity and Computing the de Rham Cohomology of Smooth Projective VarietiesFoundations of Computational Mathematics, 2012
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysisJournal of Fixed Point Theory and Applications, 2009
- Exotic Quantifiers, Complexity Classes, and Complete ProblemsFoundations of Computational Mathematics, 2007
- Computing the First Betti Number of a Semi-Algebraic SetFoundations of Computational Mathematics, 2007
- Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial TimeFoundations of Computational Mathematics, 2006
- Smoothed analysis of some condition numbersNumerical Linear Algebra with Applications, 2005
- Approximate Zeros and Condition NumbersJournal of Complexity, 1999
- Linear programming, complexity theory and elementary functional analysisMathematical Programming, 1995
- Some perturbation theory for linear programmingMathematical Programming, 1994
- Quantifier elimination for real closed fields by cylindrical algebraic decompostion1975