On the stability of computing polynomial roots via confederate linearizations
From MaRDI portal
The authors are primarily interested in the normwise stability of linearization-based root finding methods for polynomials expressed in certain nonmonomial bases (Chebyshev basis or general orthogonal polynomial basis). The paper has three main goals. First, the authors prove normwise stability when the polynomial is properly scaled and the QZ algorithm is applied to a comrade pencil associated with a Jacobi orthogonal polynomial. This study is compared with the more commonly used QR algorithm. Second, they extend a result by Arnold that leads to a first-order expansion of the backward error when the eigenvalues are computed via QR, which shows that the method can be unstable. Based on the analysis they suggest how to choose between QR and QZ. Finally, they focus on the special case of the Chebyshev basis and on the problem of finding real roots of a general function on an interval. In addition, they discuss how to compute accurate roots.
Recommendations
- Fast and backward stable computation of roots of polynomials. II: Backward error analysis; companion matrix and companion pencil
- Chebyshev rootfinding via computing eigenvalues of colleague matrices: when is it stable?
- Structured backward errors in linearizations
- Stability of rootfinding for barycentric Lagrange interpolants
- Roots of Polynomials Expressed in Terms of Orthogonal Polynomials
Cites work
- A CMV-Based Eigensolver for Companion Matrices
- A fast FFT-based discrete Legendre transform
- A note on companion matrices
- A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration
- Algorithm 610: A Portable FORTRAN Subroutine for Derivatives of the Psi Function
- Another Note on the Inclusion L p (μ) ⊂L q (μ)
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- Approximation theory and approximation practice
- Backward error and condition of polynomial eigenvalue problems
- Backward stability of polynomial root-finding using Fiedler companion matrices
- Balancing a matrix for calculation of eigenvalues and eigenvectors
- Calculation of Gauss Quadrature Rules
- Chasing bulges or rotations? A metamorphosis of the QR-algorithm
- Chebyshev interpolation for nonlinear eigenvalue problems
- Computing real roots of a polynomial in Chebyshev series form through subdivision
- Computing the common zeros of two bivariate functions via Bézout resultants
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Duality of matrix pencils, Wong chains and linearizations
- Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
- Fast and Backward Stable Computation of Roots of Polynomials
- Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations
- Fast computation of eigenvalues of companion, comrade, and related matrices
- Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank‐One Perturbations of Unitary Matrices
- Fast reduction of generalized companion matrix pairs for barycentric Lagrange interpolants
- Fiedler companion linearizations and the recovery of minimal indices
- scientific article; zbMATH DE number 3839766 (Why is no real title available?)
- scientific article; zbMATH DE number 3863589 (Why is no real title available?)
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 3491650 (Why is no real title available?)
- scientific article; zbMATH DE number 1249730 (Why is no real title available?)
- scientific article; zbMATH DE number 1821399 (Why is no real title available?)
- scientific article; zbMATH DE number 1862742 (Why is no real title available?)
- scientific article; zbMATH DE number 846277 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- scientific article; zbMATH DE number 3290249 (Why is no real title available?)
- Implicit QR for companion-like pencils
- Implicit QR for rank-structured matrix pencils
- Numerical computation of polynomial zeros by means of Aberth's method
- ON MATRICES DEPENDING ON PARAMETERS
- On orthogonal polynomials with perturbed recurrence relations
- Perturbation of the coefficients in the recurrence relation of a class of polynomials
- Perturbed recurrence relations
- Polynomial Roots from Companion Matrix Eigenvalues
- Solving a Polynomial Equation: Some History and Recent Progress
- Solving Polynomials with Small Leading Coefficients
- Solving secular and polynomial equations: a multiprecision algorithm
- Stability of rootfinding for barycentric Lagrange interpolants
- THE COLLEAGUE MATRIX, A CHEBYSHEV ANALOGUE OF THE COMPANION MATRIX
- The eigenstructure of an arbitrary polynomial matrix: Computational aspects
- Using Algebraic Geometry
- Vector spaces of linearizations for matrix polynomials: a bivariate polynomial approach
Cited in
(25)- Block Kronecker linearizations of matrix polynomials and their backward errors
- Mixed forward-backward stability of the two-level orthogonal Arnoldi method for quadratic problems
- Stable polefinding and rational least-squares fitting via eigenvalues
- On the exponential generating function for non-backtracking walks
- Matrices in companion rings, Smith forms, and the homology of 3-dimensional Brieskorn manifolds
- A note on generalized companion pencils in the monomial basis
- Revisiting the stability of computing the roots of a quadratic polynomial
- Backward error analysis of polynomial eigenvalue problems solved by linearization
- Fiedler-comrade and Fiedler-Chebyshev pencils
- Vector spaces of linearizations for matrix polynomials: a bivariate polynomial approach
- Chebyshev rootfinding via computing eigenvalues of colleague matrices: when is it stable?
- Solving Polynomials with Small Leading Coefficients
- scientific article; zbMATH DE number 7351296 (Why is no real title available?)
- Rank-Structured QR for Chebyshev Rootfinding
- Structure-preserving function approximation via convex optimization
- Fast and Backward Stable Computation of Roots of Polynomials
- Constructing strong linearizations of matrix polynomials expressed in Chebyshev bases
- A Fast Algorithm for Computing Macaulay Null Spaces of Bivariate Polynomial Systems
- On generating Sobolev orthogonal polynomials
- Finding roots of complex analytic functions via generalized colleague matrices
- Numerical instability of algebraic rootfinders
- A hidden variable resultant method for the polynomial multiparameter eigenvalue problem
- Smith forms of matrices in companion rings, with group theoretic and topological applications
- Parameterizing intersecting surfaces via invariants
- Structured backward errors in linearizations
This page was built for publication: On the stability of computing polynomial roots via confederate linearizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2814445)
