Accelerated approximation of the complex roots and factors of a univariate polynomial
From MaRDI portal
Publication:2357367
DOI10.1016/J.TCS.2017.03.030zbMATH Open1375.65066arXiv1501.05392OpenAlexW2962978702MaRDI QIDQ2357367FDOQ2357367
Authors: Victor Y. Pan, Elias P. Tsigaridas 
Publication date: 13 June 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1501.05392
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
algorithmcomplexityrootsnumerical stabilitypower sumsroot-findingcomplexity boundpolynomial equationcomplex univariate polynomialroot-refinement
Complexity and performance of numerical algorithms (65Y20) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of roots of polynomial equations (65H04)
Cites Work
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Numerical computation of polynomial zeros by means of Aberth's method
- Title not available (Why is that?)
- Convergence conditions of some methods for the simultaneous computation of polynomial zero
- Title not available (Why is that?)
- Numerical methods for roots of polynomials. Part I
- Title not available (Why is that?)
- Numerical methods for roots of polynomials. II
- Solving secular and polynomial equations: a multiprecision algorithm
- Title not available (Why is that?)
- Factorization of the Covariance Generating Function of a Pure Moving Average Process
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- Real and complex polynomial root-finding by means of eigen-solving
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- A 2002 update of the supplementary bibliography on roots of polynomials
- Efficient polynomial root-refiners: a survey and new record efficiency estimates
- Title not available (Why is that?)
- On the Boolean complexity of real root refinement
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- Nearly optimal refinement of real roots of a univariate polynomial
- An iterated eigenvalue algorithm for approximating roots of univariate polynomials
- A Newton-Raphson method for moving-average spectral factorization using the Euclid algorithm
- The Euclid algorithm and the fast computation of cross-covariance and autocovariance sequences
- Title not available (Why is that?)
- Fast approximate computations with Cauchy matrices and polynomials
- A fast version of the Schur-Cohn algorithm.
- Dandelin, Lobacevskii, or Graeffe
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
- Title not available (Why is that?)
- A new fast root-finder for black box polynomials
- Title not available (Why is that?)
- From approximate factorization to root isolation
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
Uses Software
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)
