Real polynomial root-finding by means of matrix and polynomial iterations
From MaRDI portal
Publication:2879337
Abstract: Univariate polynomial root-finding is a classical subject, still important for modern computing. Frequently one seeks just the real roots of a polynomial with real coefficients. They can be approximated at a low computational cost if the polynomial has no nonreal roots, but for high degree polynomials, nonreal roots are typically much more numerous than the real ones. The challenge is known for a long time, and the subject has been intensively studied. Nevertheless, we produce some novel ideas and techniques and obtain dramatic acceleration of the known algorithms. In order to achieve our progress we exploit the correlation between the computations with matrices and polynomials, randomized matrix computations, and complex plane geometry, extend the techniques of the matrix sign iterations, and use the structure of the companion matrix of the input polynomial. The results of our extensive tests with benchmark polynomials and random matrices are quite encouraging. In particular in our tests the number of iterations required for convergence of our algorithms grew very slowly (if at all) as we increased the degree of the univariate input polynomials and the dimension of the input matrices from 64 to 1024.
Recommendations
- Real polynomial root-finding by means of matrix and polynomial iterations
- Faulty sets of Boolean formulas and ukasiewicz logic
- New progress in real and complex polynomial root-finding
- Real and complex polynomial root-finding by means of eigen-solving
- Real arithmetic versions of simultaneous iteration methods for polynomial root finding
Cited in
(20)- A direct method to obtain a realization of a polynomial matrix and its applications
- Computation of dominant real roots of polynomials
- Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real
- Real arithmetic versions of simultaneous iteration methods for polynomial root finding
- Computing real roots of a polynomial in Chebyshev series form through subdivision with linear testing and cubic solves
- New progress in real and complex polynomial root-finding
- A fitting algorithm for real coefficient polynomial rooting
- scientific article; zbMATH DE number 3220762 (Why is no real title available?)
- Faulty sets of Boolean formulas and ukasiewicz logic
- On Matrix Polynomials with Real Roots
- Real polynomial root-finding by means of matrix and polynomial iterations
- Real root finding for determinants of linear matrices
- Computing Real Roots of Real Polynomials ... and now For Real!
- A Fourier Companion Matrix (Multiplication Matrix) with Real-Valued Elements: Finding the Roots of a Trigonometric Polynomial by Matrix Eigensolving
- Real polynomial iterative roots in the case of nonmonotonicity height \(\geqslant 2\)
- Finding all real roots of a polynomial by matrix algebra and the Adomian decomposition method
- Real and complex polynomial root-finding with eigen-solving and preprocessing
- Nearly optimal refinement of real roots of a univariate polynomial
- The polynomial pivots as initial values for a new root-finding iterative method
- Finding roots by deflated polynomial approximation
This page was built for publication: Real polynomial root-finding by means of matrix and polynomial iterations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2879337)
