Accelerated approximation of the complex roots and factors of a univariate polynomial
From MaRDI portal
Publication:2357367
Abstract: The algorithms of Pan (1995) and(2002) approximate the roots of a complex univariate polynomial in nearly optimal arithmetic and Boolean time but require precision of computing that exceeds the degree of the polynomial. This causes numerical stability problems when the degree is large. We observe, however, that such a difficulty disappears at the initial stage of the algorithms, and in our present paper we extend this stage to root-finding within a nearly optimal arithmetic and Boolean complexity bounds provided that some mild initial isolation of the roots of the input polynomial has been ensured. Furthermore our algorithm is nearly optimal for the approximation of the roots isolated in a fixed disc, square or another region on the complex plane rather than all complex roots of a polynomial. Moreover the algorithm can be applied to a polynomial given by a black box for its evaluation (even if its coefficients are not known); it promises to be of practical value for polynomial root-finding and factorization, the latter task being of interest on its own right. We also provide a new support for a winding number algorithm, which enables extension of our progress to obtaining mild initial approximations to the roots. We conclude with summarizing our algorithms and their extension to the approximation of isolated multiple roots and root clusters.
Recommendations
- Accelerated approximation of the complex roots of a univariate polynomial
- Univariate polynomials, nearly optimal algorithms for factorization and rootfinding
- Simple and nearly optimal polynomial root-finding by means of root radii approximation
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- From approximate factorization to root isolation
Cites work
- scientific article; zbMATH DE number 3839766 (Why is no real title available?)
- scientific article; zbMATH DE number 3179103 (Why is no real title available?)
- scientific article; zbMATH DE number 3489473 (Why is no real title available?)
- scientific article; zbMATH DE number 1263253 (Why is no real title available?)
- scientific article; zbMATH DE number 653122 (Why is no real title available?)
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- A 2002 update of the supplementary bibliography on roots of polynomials
- A Newton-Raphson method for moving-average spectral factorization using the Euclid algorithm
- A fast version of the Schur-Cohn algorithm.
- An iterated eigenvalue algorithm for approximating roots of univariate polynomials
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- Convergence conditions of some methods for the simultaneous computation of polynomial zero
- Dandelin, Lobacevskii, or Graeffe
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Efficient polynomial root-refiners: a survey and new record efficiency estimates
- Factorization of the Covariance Generating Function of a Pure Moving Average Process
- Fast approximate computations with Cauchy matrices and polynomials
- Nearly optimal refinement of real roots of a univariate polynomial
- Numerical computation of polynomial zeros by means of Aberth's method
- Numerical methods for roots of polynomials. II
- Numerical methods for roots of polynomials. Part I
- On the Boolean complexity of real root refinement
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Real and complex polynomial root-finding by means of eigen-solving
- Solving secular and polynomial equations: a multiprecision algorithm
- The Euclid algorithm and the fast computation of cross-covariance and autocovariance sequences
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
Cited in
(16)- Accelerated approximation of the complex roots of a univariate polynomial
- \texttt{PTOPO}: computing the geometry and the topology of parametric curves
- Multilinear polynomial systems: root isolation and bit complexity
- Accelerated subdivision for clustering roots of polynomials given by evaluation oracles
- Faster numerical univariate polynomial root-finding by means of subdivision iterations
- Simple and nearly optimal polynomial root-finding by means of root radii approximation
- A nearly optimal algorithm to decompose binary forms
- Real polynomial root-finding by means of matrix and polynomial iterations
- Univariate polynomials, nearly optimal algorithms for factorization and rootfinding
- An adaptive subdivision method for root finding of univariate polynomials
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- scientific article; zbMATH DE number 1262457 (Why is no real title available?)
- A new fast root-finder for black box polynomials
- scientific article; zbMATH DE number 1793930 (Why is no real title available?)
- From approximate factorization to root isolation
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
This page was built for publication: Accelerated approximation of the complex roots and factors of a univariate polynomial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2357367)
