Fast and Backward Stable Computation of Roots of Polynomials, Part II: Backward Error Analysis; Companion Matrix and Companion Pencil

DOI10.1137/17M1152802zbMath1398.65056arXiv1611.02435OpenAlexW2885715079MaRDI QIDQ4584920

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

Publication date: 5 September 2018

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

Full work available at URL: https://arxiv.org/abs/1611.02435

zbMATH Keywords

eigenvaluecompanion matrixpolynomialrootQR algorithmcompanion pencilbackward stabilityQZ algorithmcore transformationfrancis algorithm

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Eigenvalues, singular values, and eigenvectors (15A18) Numerical solution of nonlinear eigenvalue and eigenvector problems (65H17) Numerical computation of roots of polynomial equations (65H04)

Related Items (9)

Structured backward errors in linearizations ⋮ Fast and Backward Stable Computation of Roots of Polynomials, Part II: Backward Error Analysis; Companion Matrix and Companion Pencil ⋮ A real QZ algorithm for structured companion pencils ⋮ On pole-swapping algorithms for the eigenvalue problem ⋮ Semi-analytical solutions for eigenvalue problems of chains and periodic graphs ⋮ Sampling the eigenvalues of random orthogonal and unitary matrices ⋮ Pole-swapping algorithms for alternating and palindromic eigenvalue problems ⋮ A note on generalized companion pencils in the monomial basis ⋮ Rank-Structured QR for Chebyshev Rootfinding

Uses Software

• Matlab
• mctoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Implicit QR with compression
• Companion matrix patterns
• A fast implicit QR eigenvalue algorithm for companion matrices
• Fast and stable unitary QR algorithm
• Computational methods of linear algebra
• A bibliography on roots of polynomials
• A real QZ algorithm for structured companion pencils
• The eigenstructure of an arbitrary polynomial matrix: Computational aspects
• Solving secular and polynomial equations: a multiprecision algorithm
• An extension of the \(QZ\) algorithm beyond the Hessenberg-upper triangular pencil
• Fast computation of eigenvalues of companion, comrade, and related matrices
• Balancing a matrix for calculation of eigenvalues and eigenvectors
• Performance of the QZ Algorithm in the Presence of Infinite Eigenvalues
• Backward stability of polynomial root-finding using Fiedler companion matrices
• Implicit QR for companion-like pencils
• A note on companion pencils
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
• The Combination Shift $QZ$ Algorithm
• Fast and Backward Stable Computation of Roots of Polynomials, Part II: Backward Error Analysis; Companion Matrix and Companion Pencil
• Solving Polynomials with Small Leading Coefficients
• Accuracy and Stability of Numerical Algorithms
• Polynomial Roots from Companion Matrix Eigenvalues
• Fast Computation of the Zeros of a Polynomial via Factorization of the Companion Matrix
• Fast and Backward Stable Computation of Roots of Polynomials
• Vector Spaces of Linearizations for Matrix Polynomials
• The Matrix Eigenvalue Problem
• An Algorithm for Generalized Matrix Eigenvalue Problems

This page was built for publication: Fast and Backward Stable Computation of Roots of Polynomials, Part II: Backward Error Analysis; Companion Matrix and Companion Pencil