On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials

Real polynomials: location of zeros (26C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to systems of equations (65H10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

On the worst-case arithmetic complexity of approximating zeros of polynomials
On the Complexity of Polynomial Zeros
Optimal and nearly optimal algorithms for approximating polynomial zeros
On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
Fast computation of zeros of polynomial systems with bounded degree under finite-precision
Algebraic complexity of computing polynomial zeros
On the zero-free polynomial approximation problem
Sequential and parallel complexity of approximate evaluation of polynomial zeros
Sharper complexity bounds for zero-dimensional Gröbner bases and polynomial system solving
Approximate zero polynomials of polynomial matrices and linear systems

Cited in

(25)

On the asymptotic and practical complexity of solving bivariate systems over the reals
Algebraic complexity of computing polynomial zeros
Sequential and parallel complexity of approximate evaluation of polynomial zeros
On the worst-case arithmetic complexity of approximating zeros of polynomials
Complexity of functions: Some questions, conjectures, and results
Effective Łojasiewicz inequalities in semialgebraic geometry
Counting connected components of a semialgebraic set in subexponential time
Specified precision polynomial root isolation is in NC
On solving univariate sparse polynomials in logarithmic time
Matrices in elimination theory
Solving degenerate sparse polynomial systems faster
Probing the arrangement of hyperplanes
Systems of rational polynomial equations have polynomial size approximate zeros on the average
Optimal and nearly optimal algorithms for approximating polynomial zeros
Multivariate polynomials, duality, and structured matrices
On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae
Probing a set of hyperplanes by lines and related problems
Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
Finding connected components of a semialgebraic set in subexponential time
Finding connected components of a semialgebraic set in subexponential time
Rigid continuation paths II. structured polynomial systems
On a problem posed by Steve Smale
Continuous alternation: the complexity of pursuit in continuous domains
Generalised characteristic polynomials

This page was built for publication: On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3831940)