Pole-Swapping Algorithms for Alternating and Palindromic Eigenvalue Problems
Tóm tắt
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.
Tài liệu tham khảo
Apel, T., Mehrmann, V., Watkins, D.S.: Structured eigenvalue methods for the computation of corner singularities in 3d anisotropic elastic structures. Comput. Methods Appl. Mech. Eng. 191, 4459–4473 (2002)
Aurentz, J.L., Mach, T., Robol, L., Vandebril, R., Watkins, D.S.: Core-Chasing Algorithms for the Eigenvalue Problem. SIAM, Philadelphia (2018)
Aurentz, J.L., Mach, T., Robol, L., Vandebril, R., Watkins, D.S.: 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)
Aurentz, J.L., Mach, T., Robol, L., Vandebril, R., Watkins, D.S.: Fast and backward stable computation of the eigenvalues and eigenvectors of matrix polynomials. Math. Comp. 88, 313–347 (2019)
Aurentz, J.L., Mach, T., Vandebril, R., Watkins, D.S.: Fast and backward stable computation of roots of polynomials. SIAM J. Matrix Anal. Appl. 36, 942–973 (2015)
Bai, Z., Demmel, J.W.: On swapping diagonal blocks in real Schur form. Linear Algebra Appl. 186, 73–95 (1993)
Camps, D.: Pole Swapping Methods for the Eigenvalue Problem: Rational QR Algorithms. PhD thesis, KU Leuven (2019)
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)
Camps, D., Meerbergen, K., Vandebril, R.: A rational QZ method. SIAM J. Matrix Anal. Appl. 40, 943–972 (2019)
Camps, D., Meerbergen, K., Vandebril, R.: A multishift, multipole rational QZ method with aggressive early deflation. arXiv:1902.10954 (2019). Submitted for publication
Francis, J.G.F.: The QR transformation—part II. Comput. J. 4, 332–345 (1962)
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)
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)
Kressner, D., Schröder, C., Watkins, D.S.: Implicit QR algorithms for palindromic and even eigenvalue problems. Numer. Algorithms 51, 209–238 (2009)
Mackey, D.S., Mackey, N., Mehl, C., Mehrmann, V.: Structured polynomial eigenvalue problems: Good vibrations from good linearizations. SIAM J. Matrix Anal. Appl. 28, 1029–1051 (2006)
Mackey, D.S., Mackey, N., Mehl, C., Mehrmann, V.: Vector spaces of linearizations for matrix polynomials. SIAM J. Matrix Anal. Appl. 28, 971–1004 (2006)
Mackey, D.S., 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)
Mehrmann, V., Watkins, D.S.: Structure-preserving methods for computing eigenpairs of large sparse skew-Hamiltonian/Hamiltonian pencils. SIAM J. Sci. Comput. 22, 1905–1925 (2001)
Mehrmann, V., Watkins, D.S.: Polynomial eigenvalue problems with Hamiltonian structure. Electron. Trans. Numer. Anal. 13, 106–118 (2002)
Mehrmann, V.L.: The Autonomous Linear Quadratic Control Problem: Theory and Numerical Solution. Lecture Notes in Control and Information Sciences, vol. 163. Springer, Berlin (1991)
Moler, C.B., Stewart, G.W.: An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal. 10, 241–256 (1973)
Stewart, G.W.: On the sensitivity of the eigenvalue problem Ax = λBx. SIAM J. Numer. Anal. 9, 669–686 (1972)
Stewart, G.W.: Error and perturbation bounds for subspaces associated with certain eigenvalue problems. SIAM Rev. 15, 727–764 (1973)
Van Dooren, P.: A generalized eigenvalue approach for solving Riccati equations. SIAM J. Sci. Stat. Comput. 2, 121–135 (1981)
Vandebril, R., Watkins, D.S.: An extension of the QZ algorithm beyond the Hessenberg-upper triangular pencil. Electron. Trans. Numer. Anal. 40, 17–35 (2013)
Watkins, D.S.: The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. SIAM, Philadelphia (2007)
Watkins, D.S.: Fundamentals of Matrix Computations, 3rd edn. Wiley, New York (2010)
Watkins, D.S.: Francis’s algorithm. Amer. Math. Mon. 118, 387–403 (2011)
Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Clarendon Press, Oxford (1965)