Computing the homology of real projective sets
From MaRDI portal
Publication:667646
DOI10.1007/s10208-017-9358-8zbMath1506.55014arXiv1602.02094OpenAlexW2962955948MaRDI QIDQ667646
Michael Shub, Felipe Cucker, Teresa Krick
Publication date: 1 March 2019
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1602.02094
Analysis of algorithms (68W40) Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20) Simplicial sets and complexes in algebraic topology (55U10)
Related Items
Functional norms, condition numbers and numerical algorithms in algebraic geometry, On the complexity of the Plantinga-Vegter algorithm, Condition numbers for the cube. I: Univariate polynomials and hypersurfaces, Sampling and homology via bottlenecks, Low-degree approximation of random polynomials, Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions, Computing the homology of semialgebraic sets. I: Lax formulas, Computing the homology of semialgebraic sets. II: General formulas, Smoothed analysis for the condition number of structured real polynomial systems
Uses Software
Cites Work
- A numerical algorithm for zero counting. III: Randomization and condition
- Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time
- Computing the first Betti number of a semi-algebraic set
- A numerical algorithm for zero counting. I: Complexity and accuracy
- Exotic quantifiers, complexity classes, and complete problems
- Complexity theory of numerical linear algebra
- 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
- Some perturbation theory for linear programming
- Complexity of Bezout's theorem. V: Polynomial time
- Linear programming, complexity theory and elementary functional analysis
- Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties
- Approximate zeros and condition numbers
- Average-case complexity without the black swans
- Complexity of Bezout's theorem. III: Condition number and packing
- On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- Finding the homology of submanifolds with high confidence from random samples
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Solving linear programs with finite precision. II: Algorithms
- A Primal-Dual Algorithm for Solving Polyhedral Conic Systems with a Finite-Precision Machine
- Numerical Instability of Resultant Methods for Multidimensional Rootfinding
- Condition
- Heights of varieties in multiprojective spaces and arithmetic Nullstellensatze
- Complexity estimates depending on condition and round-off error
- Smoothed analysis of some condition numbers
- The Probability That a Numerical Analysis Problem is Difficult
- Complexity of Bezout's Theorem I: Geometric Aspects
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- On the volume of tubular neighborhoods of real algebraic varieties
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
