A rational QZ method

DOI10.1137/18M1170480zbMATH Open1420.65044arXiv1802.04094OpenAlexW2963009163WikidataQ127394544 ScholiaQ127394544MaRDI QIDQ5232124FDOQ5232124

Raf Vandebril, Daan Camps, Karl Meerbergen

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

zbMATH Keywords

implicitgeneralized eigenvaluesrational Krylovrational QZ

Mathematics Subject Classification ID

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

Cites Work

• Implicit Application of Polynomial Filters in a k-Step Arnoldi Method
• Generalized Rational Krylov Decompositions with an Application to Rational Approximation
• Title not available (Why is that?)
• Numerical methods for general and structured eigenvalue problems.
• Algorithm 866
• IFISS: A Computational Laboratory for Investigating Incompressible Flow Problems
• Rational Krylov sequence methods for eigenvalue computation
• A projection method for generalized eigenvalue problems using numerical integration.
• Title not available (Why is that?)
• The principle of minimized iterations in the solution of the matrix eigenvalue problem
• Rational Krylov algorithms for nonsymmetric eigenvalue problems. II: Matrix pairs
• The Matrix Eigenvalue Problem
• Title not available (Why is that?)
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
• A Generalized Eigenvalue Approach for Solving Riccati Equations
• Rational Krylov: A Practical Algorithm for Large Sparse Nonsymmetric Matrix Pencils
• 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
• An extension of the \(QZ\) algorithm beyond the Hessenberg-upper triangular pencil
• A Generalization of the Multishift QR Algorithm
• Nonlinear eigenvalue problems and contour integrals
• Multishift Variants of the QZ Algorithm with Aggressive Early Deflation
• Theory of Decomposition and Bulge-Chasing Algorithms for the Generalized Eigenvalue Problem
• The Combination Shift $QZ$ Algorithm
• Some Thoughts on the QZ Algorithm for Solving the Generalized Eigenvalue Problem
• Performance of the QZ algorithm in the presence of infinite eigenvalues
• Bulge Exchanges in Algorithms of QR Type
• Using implicitly filtered RKS for generalised eigenvalue problems
• The implicit application of a rational filter in the RKS method
• Francis’s Algorithm

Cited In (10)

• Swapping \(2 \times 2\) blocks in the Schur and generalized Schur form
• Generation of orthogonal rational functions by procedures for structured matrices
• Pole-swapping algorithms for alternating and palindromic eigenvalue problems
• Performance of the QZ algorithm in the presence of infinite eigenvalues
• Accurate Computation of Generalized Eigenvalues of Regular SR-BP Pairs
• Rational QZ steps with perfect shifts
• A Multishift, Multipole Rational QZ Method with Aggressive Early Deflation
• An implicit filter for rational Krylov using core transformations
• Title not available (Why is that?)
• On pole-swapping algorithms for the eigenvalue problem

Uses Software

• eigs
• MatrixMarket
• FEAST
• IFISS
• IRAM

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)