nach oben

Calcolo

Erschienen in:

01.09.2017

An extended Hamiltonian QR algorithm

verfasst von: Micol Ferranti, Bruno Iannazzo, Thomas Mach, Raf Vandebril

Erschienen in: Calcolo | Ausgabe 3/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

An extended QR algorithm specifically tailored for Hamiltonian matrices is presented. The algorithm generalizes the customary Hamiltonian QR algorithm with additional freedom in choosing between various possible extended Hamiltonian Hessenberg forms. We introduced in Ferranti et al. (Calcolo, 2015. doi:10.1007/s10092-016-0192-1) an algorithm to transform certain Hamiltonian matrices to such forms. Whereas the convergence of the classical QR algorithm is related to classical Krylov subspaces, convergence in the extended case links to extended Krylov subspaces, resulting in a greater flexibility, and possible enhanced convergence behavior. Details on the implementation, covering the bidirectional chasing and the bulge exchange based on rotations are presented. The numerical experiments reveal that the convergence depends on the selected extended forms and illustrate the validity of the approach.

Vorheriger Artikel A posteriori error analysis of an augmented mixed-primal formulation for the stationary Boussinesq model

CMV matrices are already around for a long time, e.g., [20, 33], but they acquired their name recently from the initials Cantero, Moral, and Velazquez [13].

In [15] also another type of factorization, the ascending type, is presented, where essentially the two outer matrices of (2.1) are swapped. The algorithm described in this article works also for these matrices without significant changes. In order to keep things simple we have opted to describe the algorithm for one factorization only.

We have not taken a randomly upper triangular matrix as they are typically very ill-conditioned.

Ammar, G.S., Mehrmann, V.: On Hamiltonian and symplectic Hessenberg forms. Linear Algebra Appl. 149, 55–72 (1991)MathSciNetCrossRefMATH

Aurentz, J. L., Mach, T., Vandebril, R., Watkins, D. S.: eiscor – eigenvalue solvers based on core transformations. https://github.com/eiscor/eiscor, 2014–2016

Benner, P.: Symplectic balancing of Hamiltonian matrices. SIAM J. Sci. Comput. 22, 1885–1904 (2001)MathSciNetCrossRefMATH

Benner, P., Kressner, D.: Balancing sparse Hamiltonian eigenproblems. Linear Algebra Appl. 415, 3–19 (2006)MathSciNetCrossRefMATH

Benner, P., Kressner, D., Mehrmann, V.: Skew-Hamiltonian and Hamiltonian eigenvalue problems: Theory, algorithms and applications. In: Drmač, Z., Marušić, M., Tutek, Z. (eds.) Proceedings of the Conference on Applied Mathematics and Scientific Computing, pp. 3–39. Springer, Netherlands (2005)

Benner, P., Laub, A.J., Mehrmann, V.: A collection of benchmark examples for the numerical solution of algebraic Riccati equations I: Continuous-time case, Preprints on Scientific Parallel Computing SPC 95–22, TU Chemnitz (1995)

Benner, P., Mehrmann, V., Xu, H.: A new method for computing the stable invariant subspace of a real Hamiltonian matrix. J. Comput. Appl. Math. 86, 17–43 (1997)MathSciNetCrossRefMATH

Bini, D.A., Iannazzo, B., Meini, B.: Numerical Solution of Algebraic Riccati Equations. SIAM, Philadelphia (2012)MATH

Braman, K., Byers, R., Mathias, R.: The multishift QR algorithm. Part I: maintaining well-focused shifts and level 3 performance. SIAM J. Matrix Anal. Appl. 23, 929–947 (2002)MathSciNetCrossRefMATH

10.

Braman, K., Byers, R., Mathias, R.: The multishift QR algorithm. Part II: aggressive early deflation. SIAM J. Matrix Anal. Appl. 23, 948–973 (2002)MathSciNetCrossRefMATH

11.

Bunse-Gerstner, A.: An analysis of the HR algorithm for computing the eigenvalues of a matrix. Linear Algebra Appl. 35, 155–173 (1981)MathSciNetCrossRefMATH

12.

Byers, R.: A Hamiltonian \({QR}\)-algorithm. SIAM J. Sci. Stat. Comput. 7, 212–229 (1986)MathSciNetCrossRefMATH

13.

Cantero, M.J., Moral, L., Velazquez, L.: Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle. Linear Algebra Appl. 362, 29–56 (2003)MathSciNetCrossRefMATH

14.

Chu, D., Liu, X., Mehrmann, V.: A numerical method for computing the Hamiltonian Schur form. Numer. Math. 105, 375–412 (2007)MathSciNetCrossRefMATH

15.

Ferranti, M., Iannazzo, B., Mach, T., Vandebril, R.: An extended Hessenberg form for Hamiltonian matrices. Calcolo (2015). doi:10.1007/s10092-016-0192-1 MATH

16.

Ferranti, M., Mach, T., Vandebril, R.: Extended Hamiltonian Hessenberg matrices arise in projection based model order reduction. Proc. Appl. Math. Mech. 15, 583–584 (2015)CrossRef

17.

Francis, J.G.F.: The QR transformation a unitary analogue to the LR transformation—Part 1. Comput. J. 4, 265–271 (1961)MathSciNetCrossRefMATH

18.

Francis, J.G.F.: The QR transformation—Part 2. Comput. J. 4, 332–345 (1962)MathSciNetCrossRef

19.

Karlsson, L., Kressner, D., Lang, B.: Optimally packed chains of bulges in multishift QR algorithms. ACM Trans. Math. Softw. 40(2), 12 (2014)

20.

Kimura, H.: Generalized Schwarz form and lattice-ladder realizations of digital filters. IEEE Trans. Circuits Syst. 32, 1130–1139 (1985)CrossRefMATH

21.

Kressner, D.: Numerical Methods for General and Structured Eigenvalue Problems, vol. 46 of Lecture Notes in Computational Science and Engineering. Springer, Berlin (2005)

22.

Laub, A.J.: A Schur method for solving algebraic Riccati equations. IEEE Trans. Autom. Control 24, 913–921 (1979)MathSciNetCrossRefMATH

23.

Mach, T., Pranić, M.S., Vandebril, R.: Computing approximate extended Krylov subspaces without explicit inversion. Electron. Trans. Numer. Anal. 40, 414–435 (2013)MathSciNetMATH

24.

Mach, T., Van Barel, M., Vandebril, R.: Inverse eigenvalue problems linked to rational Arnoldi, and rational (non)symmetric Lanczos. J. Comput. Appl. Math. 272, 377–398 (2014)MathSciNetCrossRefMATH

25.

Mach, T., Vandebril, R.: On deflations in extended QR algorithms. SIAM J. Matrix Anal. Appl. 35, 559–579 (2014)MathSciNetCrossRefMATH

26.

Mehrmann, V.: The Autonomous Linear Quadratic Control Problem: Theory and Numerical Solution, vol. 163 of Lecture Notes in Control and Information Sciences, Springer, Berlin (1991)

27.

Mehrmann, V., Schröder, C., Watkins, D.S.: A new block method for computing the Hamiltonian Schur form. Linear Algebra Appl. 431, 350–368 (2009)MathSciNetCrossRefMATH

28.

Paige, C., Van Loan, C.: A Schur decomposition for Hamiltonian matrices. Linear Algebra Appl. 41, 11–32 (1981)MathSciNetCrossRefMATH

29.

Tisseur, F.: Stability of structured Hamiltonian eigensolvers. SIAM J. Matrix Anal. Appl. 23, 103–125 (2001)MathSciNetCrossRefMATH

30.

Vandebril, R.: Chasing bulges or rotations? A metamorphosis of the QR-algorithm. SIAM J. Matrix Anal. Appl. 32, 217–247 (2011)MathSciNetCrossRefMATH

31.

Vandebril, R., Watkins, D.S.: A generalization of the multishift QR algorithm. SIAM J. Matrix Anal. Appl. 33, 759–779 (2012)MathSciNetCrossRefMATH

32.

Watkins, D.S.: Bidirectional chasing algorithms for the eigenvalue problem. SIAM J. Matrix Anal. Appl. 14, 166–179 (1993)MathSciNetCrossRefMATH

33.

Watkins, D.S.: Some perspectives on the eigenvalue problem. SIAM Rev. 35, 430–471 (1993)MathSciNetCrossRefMATH

34.

Watkins, D.S.: The transmission of shifts and shift blurring in the \({QR}\) algorithm. Linear Algebra Appl. 241–243, 877–896 (1996)MathSciNetCrossRefMATH

35.

Watkins, D.S.: Bulge exchanges in algorithms of \({QR}\)-type. SIAM J. Matrix Anal. Appl. 19, 1074–1096 (1998)MathSciNetCrossRefMATH

36.

Watkins, D.S.: A case where balancing is harmful. Electron. Trans. Numer. Anal. 23, 1–4 (2006)MathSciNetMATH

37.

Watkins, D.S.: On the reduction of a Hamiltonian matrix to Hamiltonian Schur form. Electron. Trans. Numer. Anal. 23, 141–157 (2006)MathSciNetMATH

38.

Watkins, D.S.: The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. SIAM, Philadelphia (2007)CrossRefMATH

39.

Watkins, D.S.: Francis’s algorithm. Am. Math. Mon. 118, 387–403 (2011)MathSciNetCrossRefMATH

40.

Wilkinson, J.H.: The Algebraic Eigenvalue Problem, Numerical Mathematics and Scientific Computation. Oxford University Press, New York (1988)

Titel: An extended Hamiltonian QR algorithm
verfasst von: Micol Ferranti
Bruno Iannazzo
Thomas Mach
Raf Vandebril
Publikationsdatum: 01.09.2017
Verlag: Springer Milan
Erschienen in: Calcolo / Ausgabe 3/2017
Print ISSN: 0008-0624
Elektronische ISSN: 1126-5434
DOI: https://doi.org/10.1007/s10092-017-0220-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2017

A posteriori error analysis of an augmented mixed-primal formulation for the stationary Boussinesq model

Discrete p-robust -liftings and a posteriori estimates for elliptic problems with source terms

A new class of nonmonotone adaptive trust-region methods for nonlinear equations with box constraints

Numerical validation for systems of absolute value equations

Square roots of matrices

A numerical approach for solving singularly perturbed convection delay problems via exponentially fitted spline method