Real polynomial root-finding by means of matrix and polynomial iterations
From MaRDI portal
Publication:2879337
DOI10.1007/978-3-319-10515-4_24zbMATH Open1417.65129arXiv1501.05390OpenAlexW3023735669MaRDI QIDQ2879337FDOQ2879337
Authors: Victor Y. Pan 
Publication date: 8 September 2014
Published in: Computer Algebra in Scientific Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1501.05390
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
companion matrixpolynomialsFrobenius algebrareal rootsreal eigenvaluesmatrix sign iterationsquare root iterationroot squaring
Cited In (17)
- A direct method to obtain a realization of a polynomial matrix and its applications
- Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real
- Computation of dominant real roots of polynomials
- 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
- Title not available (Why is that?)
- Faulty sets of Boolean formulas and ukasiewicz logic
- On Matrix Polynomials with Real Roots
- Computing Real Roots of Real Polynomials ... and now For Real!
- Real root finding for determinants of linear matrices
- 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\)
- 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)
