A real QZ algorithm for structured companion pencils

DOI10.1007/S10092-017-0231-6MaRDI QIDQ1697282zbMATH OpenOpenAlexFDO

Authors Paola Boito, Y. Eidelman, L. Gemignani

Publication date 15 February 2018

Published in Calcolo (Search for Journal in Brave)

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

zbMATH Keywords

complexitynumerical experimentsmatrix pencileigenvalue computationquasiseparable matrixreal QZ algorithmrank-structured matrixLagrange approximationpolynomial rootfinding

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Matrix pencils (15A22) Numerical computation of roots of polynomial equations (65H04)

Abstract: We design a fast implicit real QZ algorithm for eigenvalue computation of structured companion pencils arising from linearizations of polynomial rootfinding problems. The modified QZ algorithm computes the generalized eigenvalues of an $NimesN$ structured matrix pencil using $O(N)$ flops per iteration and $O(N)$ memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.

Recommendations

• Implicit QR for companion-like pencils
• Quasiseparable structures of companion pencils under the QZ-algorithm
• A fast implicit QR eigenvalue algorithm for companion matrices
• A CMV-Based Eigensolver for Companion Matrices
• Implicit QR for rank-structured matrix pencils

Cites work

• scientific article; zbMATH DE number 1805736 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Completing a matrix when certain entries of its inverse are specified
• Fast and backward stable computation of roots of polynomials. II: Backward error analysis; companion matrix and companion pencil
• Fast reduction of generalized companion matrix pairs for barycentric Lagrange interpolants
• Implicit QR for companion-like pencils
• NLEVP, a collection of nonlinear eigenvalue problems
• Numerical algorithms based on analytic function values at roots of unity
• On a new class of structured matrices
• Preconditioned iterative methods for a class of nonlinear eigenvalue problems
• Principles for Testing Polynomial Zerofinding Programs
• Pseudozeros of polynomials and pseudospectra of companion matrices
• Robust successive computation of eigenpairs for nonlinear eigenvalue problems
• Separable type representations of matrices and fast algorithms. Volume 1. Basics. Completion problems. Multiplication and inversion algorithms
• Separable type representations of matrices and fast algorithms. Volume 2. Eigenvalue method
• Stability of rootfinding for barycentric Lagrange interpolants
• The Matrix Eigenvalue Problem

Cited in

(10)

• A fast QR algorithm for companion matrices
• Structured generalized eigenvalue condition numbers for parameterized quasiseparable matrices
• Exact computations with quasiseparable matrices
• Quasiseparable structures of companion pencils under the \(QZ\)-algorithm
• An algorithm for computing the eigenvalues of block companion matrices
• Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations
• Fast and backward stable computation of roots of polynomials. II: Backward error analysis; companion matrix and companion pencil
• Orthogonal iterations on companion-like pencils
• Factoring block Fiedler companion matrices
• Implicit QR for companion-like pencils

Describes a project that uses

Uses Software

• NLEVP

This page was built for publication: A real QZ algorithm for structured companion pencils

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1697282)