Fast and Backward Stable Computation of Roots of Polynomials

DOI10.1137/140983434zbMath1319.65034OpenAlexW1524943583MaRDI QIDQ5265003

David S. Watkins, Jared Lee Aurentz, Raf Vandebril, Thomas Mach

Publication date: 21 July 2015

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: http://nur.nu.edu.kz/handle/123456789/2225

zbMATH Keywords

eigenvaluecompanion matrixroots of polynomialsnumerical experimentQR algorithmHessenberg matrixFrancis's algorithmGivens rotators

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical computation of roots of polynomial equations (65H04)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Wiener-Hopf and spectral factorization of real polynomials by Newton's method
• Numerical computation of polynomial zeros by means of Aberth's method
• Implicit QR with compression
• A fast implicit QR eigenvalue algorithm for companion matrices
• Low rank perturbation of regular matrix polynomials
• Implicit double shift \(QR\)-algorithm for companion matrices
• Pseudozeros of polynomials and pseudospectra of companion matrices
• Effective fast algorithms for polynomial spectral factorization
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• On the shifted QR iteration applied to companion matrices
• The eigenstructure of an arbitrary polynomial matrix: Computational aspects
• An algorithm for computing the eigenvalues of block companion matrices
• Separable type representations of matrices and fast algorithms. Volume 2. Eigenvalue method
• Fast computation of eigenvalues of companion, comrade, and related matrices
• Implicit QR for rank-structured matrix pencils
• Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations
• On Deflations in Extended QR Algorithms
• An Implicit Multishift $QR$-Algorithm for Hermitian Plus Low Rank Matrices
• Francis’s Algorithm
• The uniqueness in the inverse problem for transmission eigenvalues for the spherically symmetric variable-speed wave equation
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
• Principles for Testing Polynomial Zerofinding Programs
• Polynomial Roots from Companion Matrix Eigenvalues
• Fast Computation of the Zeros of a Polynomial via Factorization of the Companion Matrix
• Differential qd Algorithm with Shifts for Rank-Structured Matrices
• Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank‐One Perturbations of Unitary Matrices
• The Matrix Eigenvalue Problem
• A CMV-Based Eigensolver for Companion Matrices

Related Items (29)

Structured backward errors in linearizations ⋮ Eigenvalue condition numbers and pseudospectra of Fiedler matrices ⋮ Extension of Chebfun to Periodic Functions ⋮ SOME ANALYTICAL AND NUMERICAL RESULTS FOR THE ZEROS OF A CLASS OF FIBONACCI-LIKE POLYNOMIALS ⋮ Spectra of Jacobi operators via connection coefficient matrices ⋮ Fast and Backward Stable Computation of Roots of Polynomials, Part II: Backward Error Analysis; Companion Matrix and Companion Pencil ⋮ On pole-swapping algorithms for the eigenvalue problem ⋮ Fast computation of eigenvalues of companion, comrade, and related matrices ⋮ Factoring Block Fiedler Companion Matrices ⋮ A Robust Numerical Path Tracking Algorithm for Polynomial Homotopy Continuation ⋮ Finding roots of complex analytic functions via generalized colleague matrices ⋮ Structured condition numbers for linear systems with parameterized quasiseparable coefficient matrices ⋮ Polynomial eigenvalue solver based on tropically scaled Lagrange linearization ⋮ Structured generalized eigenvalue condition numbers for parameterized quasiseparable matrices ⋮ Backward error measures for roots of polynomials ⋮ Pole-swapping algorithms for alternating and palindromic eigenvalue problems ⋮ Fast and backward stable computation of eigenvalues and eigenvectors of matrix polynomials ⋮ Min-max elementwise backward error for roots of polynomials and a corresponding backward stable root finder ⋮ Structured eigenvalue condition numbers for parameterized quasiseparable matrices ⋮ Fast QR iterations for unitary plus low rank matrices ⋮ Structured condition numbers for Sylvester matrix equation with parameterized quasiseparable matrices ⋮ A note on generalized companion pencils in the monomial basis ⋮ On the stability of computing polynomial roots via confederate linearizations ⋮ On the Description and Stability of Orthogonal Transformations of Rank Structured Matrices ⋮ Numerical methods for spectral theory ⋮ Data Driven Koopman Spectral Analysis in Vandermonde--Cauchy Form via the DFT: Numerical Method and Theoretical Insights ⋮ An effective implementation of a modified Laguerre method for the roots of a polynomial ⋮ Rank-Structured QR for Chebyshev Rootfinding ⋮ Orthogonal iterations on companion-like pencils

Uses Software

• mctoolbox
• na20

This page was built for publication: Fast and Backward Stable Computation of Roots of Polynomials