A real QZ algorithm for structured companion pencils

DOI10.1007/S10092-017-0231-6zbMATH Open1382.65097arXiv1608.05395OpenAlexW2511175676MaRDI QIDQ1697282FDOQ1697282

Authors: Paola Boito, Y. Eidelman, L. Gemignani 

Publication date: 15 February 2018

Published in: Calcolo (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• NLEVP, a collection of nonlinear eigenvalue problems
• Title not available (Why is that?)
• 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
• Numerical algorithms based on analytic function values at roots of unity
• Title not available (Why is that?)
• The Matrix Eigenvalue Problem
• Preconditioned iterative methods for a class of nonlinear eigenvalue problems
• On a new class of structured matrices
• Completing a matrix when certain entries of its inverse are specified
• Pseudozeros of polynomials and pseudospectra of companion matrices
• Robust successive computation of eigenpairs for nonlinear eigenvalue problems
• Principles for Testing Polynomial Zerofinding Programs
• Stability of rootfinding for barycentric Lagrange interpolants
• Fast and backward stable computation of roots of polynomials. II: Backward error analysis; companion matrix and companion pencil
• Implicit QR for companion-like pencils
• Fast reduction of generalized companion matrix pairs for barycentric Lagrange interpolants

Cited In (10)

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

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)