Fast Computation of Zeros of Polynomial Systems with Bounded Degree\n under Finite-precision

2012/05/04 by Irénée Briquel, Felipe Cucker, Briquel, Irenee +5
Computer Science · Mathematics · #65G50 #65H10 #65Y20 #Algebraic Geometry and Number Theory #Cryptography and Residue Arithmetic #FOS: Mathematics #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1205.0869

openalex publication_date 2012/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A solution for Smale's 17th problem, for the case of systems with bounded\ndegree was recently given. This solution, an algorithm computing approximate\nzeros of complex polynomial systems in average polynomial time, assumed\ninfinite precision. In this paper we describe a finite-precision version of\nthis algorithm. Our main result shows that this version works within the same\ntime bounds and requires a precision which, on the average, amounts to a\npolynomial amount of bits in the mantissa of the intervening floating-point\nnumbers.\n

Related

• Computing sharp and scalable bounds on errors in approximate zeros of univariate polynomials
• Fast evaluation and root finding for polynomials with floating-point coefficients
• Condition length and complexity for the solution of polynomial systems
• Fast Evaluation of Real and Complex Polynomials
• Fast Approximation of Polynomial Zeros and Matrix Eigenvalues