A rational QZ method
From MaRDI portal
Publication:5232124
DOI10.1137/18M1170480zbMATH Open1420.65044OpenAlexW2963009163WikidataQ127394544 ScholiaQ127394544MaRDI QIDQ5232124FDOQ5232124
Authors: Daan Camps, Karl Meerbergen, Raf Vandebril 
Publication date: 29 August 2019
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Abstract: We propose a rational QZ method for the solution of the dense, unsymmetric generalized eigenvalue problem. This generalization of the classical QZ method operates implicitly on a Hessenberg, Hessenberg pencil instead of on a Hessenberg, triangular pencil. Whereas the QZ method performs nested subspace iteration driven by a polynomial, the rational QZ method allows for nested subspace iteration driven by a rational function, this creates the additional freedom of selecting poles. In this article we study Hessenberg, Hessenberg pencils, link them to rational Krylov subspaces, propose a direct reduction method to such a pencil, and introduce the implicit rational QZ step. The link with rational Krylov subspaces allows us to prove essential uniqueness (implicit Q theorem) of the rational QZ iterates as well as convergence of the proposed method. In the proofs, we operate directly on the pencil instead of rephrasing it all in terms of a single matrix. Numerical experiments are included to illustrate competitiveness in terms of speed and accuracy with the classical approach. Two other types of experiments exemplify new possibilities. First we illustrate that good pole selection can be used to deflate the original problem during the reduction phase, and second we use the rational QZ method to implicitly filter a rational Krylov subspace in an iterative method.
Full work available at URL: https://arxiv.org/abs/1802.04094
Recommendations
- A multishift, multipole rational QZ method with aggressive early deflation
- An implicit filter for rational Krylov using core transformations
- Truncated \(QZ\) methods for large scale generalized eigenvalue problems
- Jacobi--Davidson Style QR and QZ Algorithms for the Reduction of Matrix Pencils
- Rational Krylov algorithms for nonsymmetric eigenvalue problems. II: Matrix pairs
Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Generalized Eigenvalue Approach for Solving Riccati Equations
- A generalization of the multishift QR algorithm
- A projection method for generalized eigenvalue problems using numerical integration.
- Algorithm 866
- An extension of the \(QZ\) algorithm beyond the Hessenberg-upper triangular pencil
- Bulge Exchanges in Algorithms of QR Type
- Computing approximate (block) rational Krylov subspaces without explicit inversion with extensions to symmetric matrices
- Computing eigenspaces with specified eigenvalues of a regular matrix pair \((A,B)\) and condition estimation: Theory, algorithms and software
- Francis’s Algorithm
- Generalized Rational Krylov Decompositions with an Application to Rational Approximation
- IFISS: A Computational Laboratory for Investigating Incompressible Flow Problems
- Implicit Application of Polynomial Filters in a k-Step Arnoldi Method
- Multishift Variants of the QZ Algorithm with Aggressive Early Deflation
- Nonlinear eigenvalue problems and contour integrals
- Numerical methods for general and structured eigenvalue problems.
- Performance of the QZ algorithm in the presence of infinite eigenvalues
- Rational Krylov algorithms for nonsymmetric eigenvalue problems. II: Matrix pairs
- Rational Krylov sequence methods for eigenvalue computation
- Rational Krylov: A Practical Algorithm for Large Sparse Nonsymmetric Matrix Pencils
- Some Thoughts on the QZ Algorithm for Solving the Generalized Eigenvalue Problem
- The Combination Shift $QZ$ Algorithm
- The Matrix Eigenvalue Problem
- The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
- The implicit application of a rational filter in the RKS method
- The principle of minimized iterations in the solution of the matrix eigenvalue problem
- Theory of Decomposition and Bulge-Chasing Algorithms for the Generalized Eigenvalue Problem
- Using implicitly filtered RKS for generalised eigenvalue problems
Cited In (13)
- A multishift, multipole rational QZ method with aggressive early deflation
- Swapping \(2 \times 2\) blocks in the Schur and generalized Schur form
- An extension of the \(QZ\) algorithm beyond the Hessenberg-upper triangular pencil
- Generation of orthogonal rational functions by procedures for structured matrices
- Rational Krylov for real pencils with complex eigenvalues
- Pole-swapping algorithms for alternating and palindromic eigenvalue problems
- Performance of the QZ algorithm in the presence of infinite eigenvalues
- Rational QZ steps with perfect shifts
- An implicit filter for rational Krylov using core transformations
- Twice is enough for dangerous eigenvalues
- Title not available (Why is that?)
- On pole-swapping algorithms for the eigenvalue problem
- Accurate computation of generalized eigenvalues of regular SR-BP pairs
Uses Software
This page was built for publication: A rational QZ method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232124)
