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

DOI10.1137/0218024zbMath0676.65045OpenAlexW2011374998MaRDI QIDQ3831940

James Renegar

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/8631

zbMATH Keywords

algorithmupper and lower boundszeros of systems of polynomialsworst-case arithmetic complexity

Mathematics Subject Classification ID

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

Related Items (20)

Specified precision polynomial root isolation is in NC ⋮ Algebraic complexity of computing polynomial zeros ⋮ Sequential and parallel complexity of approximate evaluation of polynomial zeros ⋮ Probing a set of hyperplanes by lines and related problems ⋮ Rigid continuation paths II. structured polynomial systems ⋮ Generalised characteristic polynomials ⋮ Complexity of functions: Some questions, conjectures, and results ⋮ Effective Łojasiewicz inequalities in semialgebraic geometry ⋮ On a problem posed by Steve Smale ⋮ Multivariate polynomials, duality, and structured matrices ⋮ Continuous alternation: the complexity of pursuit in continuous domains ⋮ Counting connected components of a semialgebraic set in subexponential time ⋮ On solving univariate sparse polynomials in logarithmic time ⋮ Finding connected components of a semialgebraic set in subexponential time ⋮ Matrices in elimination theory ⋮ Solving degenerate sparse polynomial systems faster ⋮ Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems ⋮ On the asymptotic and practical complexity of solving bivariate systems over the reals ⋮ Finding connected components of a semialgebraic set in subexponential time ⋮ Probing the arrangement of hyperplanes

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