Computing the homology of real projective sets

DOI10.1007/S10208-017-9358-8zbMATH Open1506.55014arXiv1602.02094OpenAlexW2962955948MaRDI QIDQ667646FDOQ667646

Authors: Felipe Cucker, Teresa Krick, Michael Shub 

Publication date: 1 March 2019

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1602.02094

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

zbMATH Keywords

complexityexponential timehomology groupsconditionreal projective varieties

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms (68W40) Simplicial sets and complexes in algebraic topology (55U10) Numerical computation of solutions to systems of equations (65H10)

Cites Work

• Finding the homology of submanifolds with high confidence from random samples
• Computational topology. An introduction
• Condition. The geometry of numerical algorithms
• Title not available (Why is that?)
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Some perturbation theory for linear programming
• Heights of varieties in multiprojective spaces and arithmetic nullstellensätze
• Title not available (Why is that?)
• Title not available (Why is that?)
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Smoothed analysis of some condition numbers
• The Probability That a Numerical Analysis Problem is Difficult
• Complexity of Bezout's theorem. V: Polynomial time
• Complexity of Bezout's theorem. III: Condition number and packing
• Complexity of Bezout's Theorem I: Geometric Aspects
• Title not available (Why is that?)
• Complexity estimates depending on condition and round-off error
• Exotic quantifiers, complexity classes, and complete problems
• 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
• 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 numerical algorithm for zero counting. I: Complexity and accuracy
• Linear programming, complexity theory and elementary functional analysis
• On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
• 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
• Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time
• On the volume of tubular neighborhoods of real algebraic varieties
• Approximate zeros and condition numbers
• Complexity theory of numerical linear algebra
• Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties
• Average-case complexity without the black swans
• Numerical instability of resultant methods for multidimensional rootfinding
• Title not available (Why is that?)
• Computing the first Betti number of a semi-algebraic set

Cited In (11)

• Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties
• Smoothed analysis for the condition number of structured real polynomial systems
• Effective homology and periods of complex projective hypersurfaces
• Sampling and homology via bottlenecks
• Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
• Computing the homology of semialgebraic sets. II: General formulas
• On the complexity of the Plantinga-Vegter algorithm
• Condition numbers for the cube. I: Univariate polynomials and hypersurfaces
• Computing the homology of semialgebraic sets. I: Lax formulas
• Functional norms, condition numbers and numerical algorithms in algebraic geometry
• Low-degree approximation of random polynomials

Uses Software

• CHomP

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)