Condition number based complexity estimate for solving polynomial systems

DOI10.1016/J.CAM.2010.11.018MaRDI QIDQ629539zbMATH OpenOpenAlexFDO

Authors Zhikun She, Bican Xia, Zhiming Zheng

Publication date 9 March 2011

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cam.2010.11.018

zbMATH Keywords

complexity analysiscondition numberNewton operatorreal-root-countingsystems of polynomial equations

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Numerical computation of roots of polynomial equations (65H04) Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20)

Review text

A real-root-counting based method for deciding the feasibility of systems of polynomial equations is proposed. Along with this method, a modified Newton operator is used to efficiently approximate the real solutions when the systems are feasible.

Recommendations

• A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom
• The complexity and geometry of numerically solving polynomial systems
• scientific article; zbMATH DE number 1305086
• Asymptotic acceleration of solving multivariate polynomial systems of equations
• Condition length and complexity for the solution of polynomial systems

Cites work

• A complete algorithm for counting real solutions of polynomial systems of equations and inequalities.
• A new decision method for elementary algebra
• Approximate zeros and condition numbers
• Complexity estimates depending on condition and round-off error
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Condition number based complexity estimate for computing local extrema
• scientific article; zbMATH DE number 421661 (Why is no real title available?)
• scientific article; zbMATH DE number 3846864 (Why is no real title available?)
• scientific article; zbMATH DE number 4212207 (Why is no real title available?)
• scientific article; zbMATH DE number 4214184 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 1096865 (Why is no real title available?)
• scientific article; zbMATH DE number 3992817 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Polynomial algorithms in computer algebra
• Solving systems of polynomial inequalities in subexponential time
• Sur la complexité du principe de Tarski-Seidenberg
• The complexity of elementary algebra and geometry

Cited in

(11)

• Condition number based complexity estimate for computing local extrema
• Using the method of dual quadratic solutions to solve systems of polynomial equations in the complex domain
• Discovering polynomial Lyapunov functions for continuous dynamical systems
• Validating the completeness of the real solution set of a system of polynomial equations
• A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom
• scientific article; zbMATH DE number 1305086 (Why is no real title available?)
• A condition number theorem for underdetermined polynomial systems
• A condition-based algorithm for solving polyhedral feasibility problems
• Characterizations and criteria for synchronization of heterogeneous networks to linear subspaces
• Condition length and complexity for the solution of polynomial systems
• High probability analysis of the condition number of sparse polynomial systems

This page was built for publication: Condition number based complexity estimate for solving polynomial systems

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