On pole-swapping algorithms for the eigenvalue problem

DOI10.1553/ETNA_VOL52S480zbMATH Open1456.65025arXiv1906.08672OpenAlexW3134096121MaRDI QIDQ2218921FDOQ2218921

Thomas Mach, Raf Vandebril, Daan Camps, David S. Watkins

Publication date: 18 January 2021

Published in: ETNA - Electronic Transactions on Numerical Analysis (Search for Journal in Brave)

Abstract: Pole-swapping algorithms, which are generalizations of the QZ algorithm for the generalized eigenvalue problem, are studied. A new modular (and therefore more flexible) convergence theory that applies to all pole-swapping algorithms is developed. A key component of all such algorithms is a procedure that swaps two adjacent eigenvalues in a triangular pencil. An improved swapping routine is developed, and its superiority over existing methods is demonstrated by a backward error analysis and numerical tests. The modularity of the new convergence theory and the generality of the pole-swapping approach shed new light on bi-directional chasing algorithms, optimally packed shifts, and bulge pencils, and allow the design of novel algorithms.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Pole-swapping algorithms for alternating and palindromic eigenvalue problems
• On the Schwarz alternating method for eigenvalue problems
• Publication:4489544
• scientific article; zbMATH DE number 3982395
• A stable, polynomial-time algorithm for the eigenpair problem
• scientific article; zbMATH DE number 37916
• An algorithm for solution of large eigenvalue problems
• Eigenvalues and switching algorithms for Quasi-Newton updates
• Polynomial eigenvalue problems: theory, computation, and structure

zbMATH Keywords

convergence analysisgeneralized eigenvalue problempole swapping algorithms

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Cites Work

• Generalized Rational Krylov Decompositions with an Application to Rational Approximation
• Title not available (Why is that?)
• Accuracy and Stability of Numerical Algorithms
• Implicit QR algorithms for palindromic and even eigenvalue problems
• The Matrix Eigenvalue Problem
• Title not available (Why is that?)
• LAPACK-style algorithms and software for solving the generalized Sylvester equation and estimating the separation between regular matrix pairs
• An Algorithm for Generalized Matrix Eigenvalue Problems
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
• A Generalized Eigenvalue Approach for Solving Riccati Equations
• Using Level 3 BLAS in Rotation-Based Algorithms
• The multishift QR algorithm. I: Maintaining well-focused shifts and level 3 performance
• The multishift QR algorithm. II: Aggressive early deflation
• On swapping diagonal blocks in real Schur form
• Computing eigenspaces with specified eigenvalues of a regular matrix pair \((A,B)\) and condition estimation: Theory, algorithms and software
• An extension of the \(QZ\) algorithm beyond the Hessenberg-upper triangular pencil
• A Hamiltonian $QR$ Algorithm
• Fast and Backward Stable Computation of Roots of Polynomials
• A Novel Parallel QR Algorithm for Hybrid Distributed Memory HPC Systems
• Core-Chasing Algorithms for the Eigenvalue Problem
• Fast and Backward Stable Computation of Roots of Polynomials, Part II: Backward Error Analysis; Companion Matrix and Companion Pencil
• Fast and backward stable computation of eigenvalues and eigenvectors of matrix polynomials
• Forward Stability and Transmission of Shifts in the $QR$ Algorithm
• Bulge Exchanges in Algorithms of QR Type
• Title not available (Why is that?)
• The transmission of shifts and shift blurring in the QR algorithm
• A Rational QZ Method
• Francis’s Algorithm
• Optimally packed chains of bulges in multishift QR algorithms

Cited In (3)

• Changing poles in the rational Lanczos method for the Hermitian eigenvalue problem
• Generation of orthogonal rational functions by procedures for structured matrices
• A Multishift, Multipole Rational QZ Method with Aggressive Early Deflation

Uses Software

• mctoolbox

This page was built for publication: On pole-swapping algorithms for the eigenvalue problem

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