Grid methods in computational real algebraic (and semialgebraic) geometry

DOI10.1007/s11401-018-1070-8zbMath1391.14115OpenAlexW2790809215MaRDI QIDQ1754715

Felipe Cucker

Publication date: 31 May 2018

Published in: Chinese Annals of Mathematics. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11401-018-1070-8

zbMATH Keywords

complexitynumerical algorithmssemialgebraic geometrygrid methodcondition

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Uses Software

• CHomP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A numerical algorithm for zero counting. III: Randomization and condition
• A numerical algorithm for zero counting. I: Complexity and accuracy
• Exotic quantifiers, complexity classes, and complete problems
• On condition numbers and the distance to the nearest ill-posed problem
• Complexity theory of numerical linear algebra
• Solving systems of polynomial inequalities in subexponential time
• 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 computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Complexity of deciding Tarski algebra
• Complexity of Bezout's theorem. V: Polynomial time
• A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
• Linear programming, complexity theory and elementary functional analysis
• Approximate zeros and condition numbers
• The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
• Average-case complexity without the black swans
• Complexity of Bezout's theorem. III: Condition number and packing
• 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
• Condition
• Complexity estimates depending on condition and round-off error
• Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems
• 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
• A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF
• Algorithms in real algebraic geometry

This page was built for publication: Grid methods in computational real algebraic (and semialgebraic) geometry