×

Pole-swapping algorithms for alternating and palindromic eigenvalue problems. (English) Zbl 1461.93179

Summary: Pole-swapping algorithms are generalizations of bulge-chasing algorithms for the generalized eigenvalue problem. Structure-preserving pole-swapping algorithms for the palindromic and alternating eigenvalue problems, which arise in control theory, are derived. A refinement step that guarantees backward stability of the algorithms is included. This refinement can also be applied to bulge-chasing algorithms that had been introduced previously, thereby guaranteeing their backward stability in all cases.

MSC:

93B60 Eigenvalue problems
93B55 Pole and zero placement problems
15A22 Matrix pencils
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Apel, T.; Mehrmann, V.; Watkins, DS, Structured eigenvalue methods for the computation of corner singularities in 3d anisotropic elastic structures, Comput. Methods Appl. Mech. Eng., 191, 4459-4473 (2002) · Zbl 1029.74042 · doi:10.1016/S0045-7825(02)00390-0
[2] Aurentz, JL; Mach, T.; Robol, L.; Vandebril, R.; Watkins, DS, Core-Chasing Algorithms for the Eigenvalue Problem (2018), Philadelphia: SIAM, Philadelphia · Zbl 1434.65003 · doi:10.1137/1.9781611975345
[3] Aurentz, JL; Mach, T.; Robol, L.; Vandebril, R.; Watkins, DS, 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, 1245-1269 (2018) · Zbl 1398.65056 · doi:10.1137/17M1152802
[4] Aurentz, JL; Mach, T.; Robol, L.; Vandebril, R.; Watkins, DS, Fast and backward stable computation of the eigenvalues and eigenvectors of matrix polynomials, Math. Comp., 88, 313-347 (2019) · Zbl 1434.65030 · doi:10.1090/mcom/3338
[5] Aurentz, JL; Mach, T.; Vandebril, R.; Watkins, DS, Fast and backward stable computation of roots of polynomials, SIAM J. Matrix Anal. Appl., 36, 942-973 (2015) · Zbl 1319.65034 · doi:10.1137/140983434
[6] Bai, Z.; Demmel, JW, On swapping diagonal blocks in real Schur form, Linear Algebra Appl., 186, 73-95 (1993) · Zbl 0783.65030 · doi:10.1016/0024-3795(93)90286-W
[7] Camps, D.: Pole Swapping Methods for the Eigenvalue Problem: Rational QR Algorithms. PhD thesis, KU Leuven (2019)
[8] Camps, D., Mach, T., Vandebril, R., Watkins, D.S.: On pole-swapping algorithms for the eigenvalue problem. arXiv:1906.08672 (2019). Electron Trans. Numer. Anal. (submitted)
[9] Camps, D.; Meerbergen, K.; Vandebril, R., A rational QZ method, SIAM J. Matrix Anal. Appl., 40, 943-972 (2019) · Zbl 1420.65044 · doi:10.1137/18M1170480
[10] Camps, D., Meerbergen, K., Vandebril, R.: A multishift, multipole rational QZ method with aggressive early deflation. arXiv:1902.10954 (2019). Submitted for publication · Zbl 1420.65044
[11] Francis, JGF, The QR transformation—part II, Comput. J., 4, 332-345 (1962) · doi:10.1093/comjnl/4.4.332
[12] Kågström, B.; Poromaa, P., Computing eigenspaces with specified eigenvalues of a regular matrix pair (A,b) and condition estimation: theory, algorithms and software, Numer. Algor., 12, 369-407 (1996) · Zbl 0859.65036 · doi:10.1007/BF02142813
[13] Kågström, B.; Poromaa, P., LAPACK-Style algorithms and software for solving the generalized Sylvester equation and estimating the separation between regular matrix pairs, ACM Trans. Math. Softw., 22, 78-103 (1996) · Zbl 0884.65031 · doi:10.1145/225545.225552
[14] Kressner, D.; Schröder, C.; Watkins, DS, Implicit QR algorithms for palindromic and even eigenvalue problems, Numer. Algorithms, 51, 209-238 (2009) · Zbl 1181.65054 · doi:10.1007/s11075-008-9226-3
[15] Mackey, DS; Mackey, N.; Mehl, C.; Mehrmann, V., Structured polynomial eigenvalue problems: Good vibrations from good linearizations, SIAM J. Matrix Anal. Appl., 28, 1029-1051 (2006) · Zbl 1132.65028 · doi:10.1137/050628362
[16] Mackey, DS; Mackey, N.; Mehl, C.; Mehrmann, V., Vector spaces of linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl., 28, 971-1004 (2006) · Zbl 1132.65027 · doi:10.1137/050628350
[17] Mackey, DS; Mackey, N.; Mehl, C.; Mehrmann, V., Numerical methods for palindromic eigenvalue problems: Computing the anti-triangular Schur form, Numer. Linear Algebra Appl., 16, 63-86 (2009) · Zbl 1224.65099 · doi:10.1002/nla.612
[18] Mehrmann, V.; Watkins, DS, Structure-preserving methods for computing eigenpairs of large sparse skew-Hamiltonian/Hamiltonian pencils, SIAM J. Sci. Comput., 22, 1905-1925 (2001) · Zbl 0986.65033 · doi:10.1137/S1064827500366434
[19] Mehrmann, V.; Watkins, DS, Polynomial eigenvalue problems with Hamiltonian structure, Electron. Trans. Numer. Anal., 13, 106-118 (2002) · Zbl 1065.65054
[20] Mehrmann, VL, The Autonomous Linear Quadratic Control Problem: Theory and Numerical Solution. Lecture Notes in Control and Information Sciences, vol. 163 (1991), Berlin: Springer, Berlin · Zbl 0746.93001 · doi:10.1007/BFb0039443
[21] Moler, CB; Stewart, GW, An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal., 10, 241-256 (1973) · Zbl 0253.65019 · doi:10.1137/0710024
[22] Stewart, GW, On the sensitivity of the eigenvalue problem Ax = λBx, SIAM J. Numer. Anal., 9, 669-686 (1972) · Zbl 0252.65026 · doi:10.1137/0709056
[23] Stewart, GW, Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Rev., 15, 727-764 (1973) · Zbl 0297.65030 · doi:10.1137/1015095
[24] Van Dooren, P., A generalized eigenvalue approach for solving Riccati equations, SIAM J. Sci. Stat. Comput., 2, 121-135 (1981) · Zbl 0463.65024 · doi:10.1137/0902010
[25] Vandebril, R.; Watkins, DS, An extension of the QZ algorithm beyond the Hessenberg-upper triangular pencil, Electron. Trans. Numer. Anal., 40, 17-35 (2013) · Zbl 1288.65053
[26] Watkins, DS, The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods (2007), Philadelphia: SIAM, Philadelphia · Zbl 1142.65038 · doi:10.1137/1.9780898717808
[27] Watkins, DS, Fundamentals of Matrix Computations (2010), New York: Wiley, New York · Zbl 1206.65003
[28] Watkins, DS, Francis’s algorithm, Amer. Math. Mon., 118, 387-403 (2011) · Zbl 1214.65016 · doi:10.4169/amer.math.monthly.118.05.387
[29] Wilkinson, JH, The Algebraic Eigenvalue Problem (1965), Oxford: Clarendon Press, Oxford · Zbl 0258.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.