Grid methods in computational real algebraic (and semialgebraic) geometry
type: Item
instance of: scholarly article
title: Grid methods in computational real algebraic (and semialgebraic) geometry
zbMATH Open document ID: 1391.14115
author: Felipe Cucker
published in: Chinese Annals of Mathematics. Series B
publication date: 2018-05-31T00:00:00Z
review text: As the author describes in the abstract, the numerical algorithms that have appeared in recents years to solve problems in real algebraic and semialgebraic geometry are numerically stable, ``but their complexity analysis, based on the condition of the data, is radically different from the usual complexity analysis in symbolic computation as these numerical algorithms may run forever on a thin set of ill-posed inputs''. In this paper, after a detailed overview of the development of algorithms in real algebraic and semialgebraic geometry and their computational complexity, the author considers three problems: the feasibility problem for systems of homogeneus polynomials, the problem of counting zeros for square systems of homogeneus polynomials and the problem of the computation of the homology of basic semialgebraic sets. These problems are algorithmically solved by means of grid methods. Analysis of the algorithms is also given.
reviewed by: Carlos Hermoso
Mathematics Subject Classification ID: 14Q20
Mathematics Subject Classification ID: 65H10
Mathematics Subject Classification ID: 14P10
zbMATH DE Number: 6877231
zbMATH Keywords: numerical algorithms
zbMATH Keywords: complexity
zbMATH Keywords: condition
zbMATH Keywords: semialgebraic geometry
zbMATH Keywords: grid method
describes a project that uses: CHomP
MaRDI profile type: Publication
full work available at URL: s11401-018-1070-8
OpenAlex ID: W2790809215
cites work: Q3998344
cites work: Average-case complexity without the black swans
cites work: Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems
cites work: Algorithms in real algebraic geometry
cites work: Q3996250
cites work: Q4871782
cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Q3770650
cites work: Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
cites work: Exotic quantifiers, complexity classes, and complete problems
cites work: Condition
cites work: Q5479932
cites work: Q4079605
cites work: Approximate zeros and condition numbers
cites work: A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF
cites work: A numerical algorithm for zero counting. I: Complexity and accuracy
cites work: A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
cites work: A numerical algorithm for zero counting. III: Randomization and condition
cites work: Complexity estimates depending on condition and round-off error
cites work: On condition numbers and the distance to the nearest ill-posed problem
cites work: Q4348513
cites work: Complexity of deciding Tarski algebra
cites work: Solving systems of polynomial inequalities in subexponential time
cites work: The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
cites work: Complexity theory of numerical linear algebra
cites work: A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
cites work: Q4681935
cites work: Finding the homology of submanifolds with high confidence from random samples
cites work: Q1185456
cites work: On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
cites work: On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
cites work: Incorporating Condition Measures into the Complexity Theory of Linear Programming
cites work: Linear programming, complexity theory and elementary functional analysis
cites work: Complexity of Bezout's Theorem I: Geometric Aspects
cites work: Q3135179
cites work: Complexity of Bezout's theorem. III: Condition number and packing
cites work: Complexity of Bezout's theorem. V: Polynomial time
cites work: Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
cites work: Q4720691
cites work: Q5807665
cites work: Q4337625
cites work: Q4137157
DOI: 10.1007/S11401-018-1070-8
description: scientific article; zbMATH DE number 6877231