Complexity estimates depending on condition and round-of error

DOI10.1007/3-540-68530-8_10MaRDI QIDQ4252028zbMATH OpenFDO

Authors Felipe Cucker, Stephen Smale

Publication date 11 January 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-68530-8_10

zbMATH Keywords

algorithmcomplexity estimatesloss of precisionpolynomial boundround-off errorsystems of polynomial equations

Mathematics Subject Classification ID

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) Roundoff error (65G50) Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20)

Review text

Solving systems of polynomial equations by computer has become a principal task in many areas of science. In most of this usage of the machine, there is a loss of precision at many steps of the process. For example a round-off error occurs when two numbers with 10 digit precision are multiplied to obtain a new number with 10 digit precision. The main goal of this paper is to give a theoretical foundation for solving systems of equations (with inequality constraints permitted as well) which takes into account this loss of precision. We give an algorithm with reasonable complexity estimates for solving general real polynomial systems of equalities and inequalities and which succeeds in the presence of round-off error, provided the precision of the computation satisfies a bound polynomial in some parameters (to be described). Moreover we strive to give some foundations for the round-off error in the setting of real number machines. Modifying these ``real Turing machines to include round-off error helps to make a more compelling case for their use in the foundations of numerical analysis. Our main theorem states that the feasibility of any system of equalities and inequalities in \(n\) variables can be decided in time polynomial in the condition number of the input system and singly exponential in \(n\). Moreover, a polynomial bound is given for the required precision. For the entire collection see [Zbl 0895.00050].

Recommendations

• Complexity estimates depending on condition and round-off error
• Condition number based complexity estimate for solving polynomial systems
• Fast computation of zeros of polynomial systems with bounded degree under finite-precision
• A theory of complexity, condition, and roundoff

Cited in

(8)

• On complexity of round transformations
• A real polynomial decision algorithm using arbitrary-precision floating point arithmetic
• Complexity estimates depending on condition and round-off error
• scientific article; zbMATH DE number 3994936 (Why is no real title available?)
• scientific article; zbMATH DE number 1859211 (Why is no real title available?)
• On the cost of iterative computations
• Decision problems and round-off machines
• Condition number based complexity estimate for solving polynomial systems

This page was built for publication: Complexity estimates depending on condition and round-of error

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