A Real QZ Algorithm for Structured Companion Pencils

2016/08/18 by Paola Boito, Boito, Paola, Yuli Eidelman +3
Computer Science · Mathematics · Physics and Astronomy · #65F15 #65H17 #Electromagnetic Scattering and Analysis #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Numerical methods for differential equations

paper · doi:10.48550/arxiv.1608.05395

openalex publication_date 2016/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 N× N 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.

Related

• Implicit QR for Companion-like Pencils
• Fast and backward stable computation of the eigenvalues and eigenvectors of matrix polynomials
• Fast and backward stable computation of roots of polynomials, Part II: backward error analysis; companion matrix and companion pencil
• The RQR algorithm
• New numerical algorithm for deflation of infinite and zero eigenvalues and full solution of quadratic eigenvalue problems