publication . Article . Preprint . Journal . 2020

On pole-swapping algorithms for the eigenvalue problem

Thomas Mach; David S. Watkins; Daan Camps; Raf Vandebril;
Open Access
  • Published: 01 Jan 2020
  • Publisher: eScholarship, University of California
Abstract
Copyright © 2020, Kent State University. 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-di...
Persistent Identifiers
Subjects
free text keywords: eigenvalue, QZ algorithm, pole swapping, convergence, math.NA, cs.NA, 65F15, 15A18, Numerical & Computational Mathematics, Pure Mathematics, Applied Mathematics, Numerical and Computational Mathematics, Mathematics - Numerical Analysis, 65F15, 15A18, eigenvalue, QZ algorithm, pole swapping, convergence,Mathematik, Analysis, Modular design, business.industry, business, Generalization, Pencil (mathematics), Eigenvalues and eigenvectors, Symbolic convergence theory, Computer science, Modularity, Eigendecomposition of a matrix, Algorithm, Generality
32 references, page 1 of 3

[1] J. L. Aurentz, T. Mach, L. Robol, R. Vandebril, and D. S. Watkins, Core-Chasing Algorithms for the Eigenvalue Problem, SIAM, Philadelphia, 2018. [OpenAIRE]

[2] , Fast and backward stable computation of roots of polynomials, part II: backward error analysis; companion matrix and companion pencil, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 1245-1269.

[3] , Fast and backward stable computation of the eigenvalues and eigenvectors of matrix polynomials, Math. Comp., 88 (2019), pp. 313-347.

[4] J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, Fast and backward stable computation of roots of polynomials, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 942-973. [OpenAIRE]

[5] Z. Bai and J. Demmel, On swapping diagonal blocks in real Schur form, Linear Algebra Appl., 186 (1993), pp. 73-95. [OpenAIRE]

[6] M. Berljafa and S. Gu¨ttel, Generalized rational Krylov decompositions with an application to rational approximation, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 894-916. [OpenAIRE]

[7] A. Bojanczyk and P. Van Dooren, Reordering diagonal blocks in the real Schur form, in Linear Algebra for Large Scale and Real-Time Applications, M. Moonen, G. Golub, and B. D. Moor, eds., NATO ASI Series E: Applied Sciences, Springer, 1993, pp. 351-352.

[8] K. Braman, R. Byers, and R. Matthias, The multishift QR algorithm, part I: Maintaining well focused shifts and level 3 performance, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 929-947.

[9] , The multishift QR algorithm, part II: Aggressive early deflation, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 948-973.

[10] R. Byers, Hamiltonian and Symplectic Algorithms for the Algebraic Riccati Equation, PhD thesis, Cornell University, 1983.

[11] , A Hamiltonian QR algorithm, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 212-229.

[12] D. Camps, Pole swapping methods for the eigenvalue problem: Rational QR algorithms, PhD thesis, KU Leuven, 2019.

[13] D. Camps, K. Meerbergen, and R. Vandebril, A rational QZ method, SIAM J. Matrix Anal. Appl., (2018). arXiv:1802.04094v2. to appear.

[14] , A multishift, multipole rational QZ method with aggressive early deflation. arXiv:1902.10954, 2019. submitted for publication.

[15] J. G. F. Francis, The QR transformation, part II, Computer J., 4 (1961), pp. 332-345.

32 references, page 1 of 3
Any information missing or wrong?Report an Issue