zbMATH — the first resource for mathematics

A Hamiltonian Krylov-Schur-type method based on the symplectic Lanczos process. (English) Zbl 1219.65040
The paper presents a Krylov-Schur-like restarting technique applied within the symplectic Lanczos algorithm for the Hamiltonian eigenvalue problem.
The first section is an introduction in nature.
The second and third sections briefly reviewed the symplectic Lanczos method and the Hamiltonian SR method.
The fourth section expands the new restarting technique for the symplectic Lanczos method based on Krylov-Schur-like decompositions.
The fifth section focuses on the purging and locking strategy in order to improve the convergence properties of the symplectic Lanczos algorithm.
The sixth section concerns the stopping criteria while the shift-and-invert techniques are briefly discussed in the seventh section.
In order to prove the accuracy of the eigenvalue approximations, the eight section presents the results of some numerical experiments obtained with Krylov-Schur-type method for Hamiltonian eigenproblems, performed in MATLAB R006a and concerning heat transfer equation and random phase approximation.

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
Full Text: DOI
[1] J. Abels, P. Benner, CAREX - a collection of benchmark examples for continuous-time algebraic Riccati equations (version 2.0), SLICOT Working Note 1999-14, November 1999. Available from: <www.slicot.de>.
[2] Antoulas, A., A new result on positive real interpolation and model reduction, Systems control lett., 54, 361-374, (2005) · Zbl 1129.93304
[3] Apel, T.; Mehrmann, V.; Watkins, D., Structured eigenvalue methods for the computation of corner singularities in 3D anisotropic elastic structures, Comput. methods appl. mech. engrg., 191, 4459-4473, (2002) · Zbl 1029.74042
[4] P. Benner, Computational methods for linear-quadratic optimization, Supplemento ai Rendiconti del Circolo Matematico di Palermo, Serie II, No. 58 (1999) 21-56. · Zbl 0930.65075
[5] P. Benner, Structured Krylov subspace methods for eigenproblems with spectral symmetries, in: Workshop on Theoretical and Computational Aspects of Matrix Algorithms, Schloß Dagstuhl, October 12-17, 2003, October 2003. Available from: <http://archiv.tu-chemnitz.de/pub/2010/0085>.
[6] Benner, P.; Faßbender, H., An implicitly restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem, Linear algebra appl., 263, 75-111, (1997) · Zbl 0884.65028
[7] Benner, P.; Faßbender, H., An implicitly restarted Lanczos method for the symplectic eigenvalue problem, SIAM J. matrix anal. appl., 22, 682-713, (2000) · Zbl 0985.65026
[8] Benner, P.; Faßbender, H., Numerical methods for passivity preserving model reduction, At-automatisierungstechnik, 54, 4, 153-160, (2006), (in German)
[9] Benner, P.; Faßbender, H.; Stoll, M., Solving large-scale quadratic eigenvalue problems with Hamiltonian eigenstructure using a structure-preserving Krylov subspace method, Electron. trans. numer. anal., 29, 212-229, (2007/08) · Zbl 1171.65374
[10] P. Benner, H. Faßbender, M. Stoll, A Hamiltonian Krylov-Schur-type method based on the symplectic Lanczos process, OCCAM report 09/32, Oxford Centre for Collaborative Applied Mathematics. Available from: <http://eprints.maths.ox.ac.uk/806/1/finalOR32.pdf>, July 2009.
[11] Benner, P.; Kressner, D., Algorithm 854: Fortran 77 subroutines for computing the eigenvalues of Hamiltonian matrices, ACM trans. math. software, 32, 2, 352-373, (2006) · Zbl 1365.65091
[12] P. Benner, A. Laub, V. Mehrmann, A collection of benchmark examples for the numerical solution of algebraic Riccati equations I: continuous-time case, Technical report SPC 95_22, Fakultät für Mathematik, TU Chemnitz-Zwickau, 1995.
[13] Benner, P.; Saak, J., A semi-discretized heat transfer model for optimal cooling of steel profiles, (), 353-356 · Zbl 1170.80341
[14] Boyd, S.; Balakrishnan, V.; Kabamba, P., A bisection method for computing the \(H_\infty\) norm of a transfer matrix and related problems, Math. control signals systems, 2, 207-219, (1989) · Zbl 0674.93020
[15] Bunse-Gerstner, A., Matrix factorizations for symplectic QR-like methods, Linear algebra appl., 83, 49-77, (1986) · Zbl 0616.65042
[16] Bunse-Gerstner, A.; Mehrmann, V., A symplectic QR-like algorithm for the solution of the real algebraic Riccati equation, IEEE trans. automat. control, AC-31, 1104-1113, (1986) · Zbl 0616.65048
[17] Bunse-Gerstner, A.; Mehrmann, V.; Watkins, D., An SR algorithm for Hamiltonian matrices based on Gaussian elimination, Methods oper. res., 58, 339-356, (1989) · Zbl 0701.65032
[18] Burke, J.; Lewis, A.; Overton, M., Robust stability and a criss-cross algorithm for pseudospectra, IMA J. numer. anal., 23, 359-375, (2003) · Zbl 1042.65060
[19] Byers, R., A bisection method for measuring the distance of a stable to unstable matrices, SIAM J. sci. statist. comput., 9, 875-881, (1988) · Zbl 0658.65044
[20] Calvetti, D.; Reichel, L.; Sorensen, D., An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Electron. trans. numer. anal., 2, 1-21, (1994) · Zbl 0809.65030
[21] T. Eirola, Krylov integrators for Hamiltonian systems, in: Workshop on Exponential Integrators, October 20-23, 2004 Innsbruck, Austria, 2004. Available from: <http://techmath.uibk.ac.at/numbau/alex/events/files04/slides/timo.pdf>.
[22] H. Faßbender, A detailed derivation of the parameterized SR algorithm and the symplectic Lanczos method for Hamiltonian matrices, Internal report, TU Braunschweig, Institut Computational Mathematics, 2006. Available from: <http://www.icm.tu-bs.de/hfassben/papers/ham_evp.pdf>.
[23] Faßbender, H., The parametrized SR algorithm for Hamiltonian matrices, Electron. trans. numer. anal., 26, 121-145, (2007) · Zbl 1171.65375
[24] Ferng, W.; Lin, W.-W.; Wang, C.-S., The shift-inverted J-Lanczos algorithm for the numerical solutions of large sparse algebraic Riccati equations, Comput. math. appl., 33, 23-40, (1997) · Zbl 0889.65034
[25] Francis, J., The QR transformation, part I and part II, Comput. J., 4, 265-271, (1961), 332-345 · Zbl 0104.34304
[26] Freund, R., Lanczos-type algorithms for structured non-Hermitian eigenvalue problems, (), 243-245
[27] R. Freund, V. Mehrmann, A symplectic look-ahead Lanczos algorithm for the Hamiltonian eigenvalue problem, manuscript, 1994.
[28] Golub, G.; Van Loan, C., Matrix computations, (1996), Johns Hopkins University Press Baltimore · Zbl 0865.65009
[29] Grimme, E.; Sorensen, D.; Van Dooren, P., Model reduction of state space systems via an implicitly restarted Lanczos method, Numer. algorithms, 12, 1-31, (1996) · Zbl 0870.65052
[30] Higham, N., Accuracy and stability of numerical algorithms, (1996), SIAM Publications Philadelphia, PA · Zbl 0847.65010
[31] Ito, K.; Kunisch, K., Reduced order control based on approximate inertial manifolds, Linear algebra appl., 415, 2-3, 531-541, (2006) · Zbl 1105.93018
[32] Kahan, W.; Parlett, B.; Jiang, E., Residual bounds on approximate eigensystems of nonnormal matrices, SIAM J. numer. anal., 19, 470-484, (1982) · Zbl 0483.65024
[33] Laub, A.; Meyer, K., Canonical forms for symplectic and Hamiltonian matrices, Celestial mech., 9, 213-238, (1974) · Zbl 0316.15005
[34] Lehoucq, R.; Sorensen, D., Deflation techniques for an implicitly restarted Arnoldi iteration, SIAM J. matrix anal. appl., 17, 789-821, (1996) · Zbl 0863.65016
[35] Lin, W.-W.; Mehrmann, V.; Xu, H., Canonical forms for Hamiltonian and symplectic matrices and pencils, Linear algebra appl., 302-303, 469-533, (1999) · Zbl 0947.15004
[36] Lopez, L.; Simoncini, V., Preserving geometric properties of the exponential matrix by block Krylov subspace methods, Bit, 46, 813-830, (2006) · Zbl 1107.65039
[37] Lucero, M.; Niklasson, A.; Tretiak, S.; Challacombe, M., Molecular-orbital-free algorithm for excited states in time-dependent perturbation theory, J. chem. phys., 129, 6, 064114-1-064114-8, (2008)
[38] V. Mehrmann, The Autonomous Linear Quadratic Control Problem, Theory and Numerical Solution, Number 163 in Lecture Notes in Control and Information Sciences, Springer-Verlag, Heidelberg, 1991. · Zbl 0746.93001
[39] Mehrmann, V.; Watkins, D., Structure-preserving methods for computing pairs of large sparse skew-Hamiltonian/Hamiltonian pencils, SIAM J. sci. statist. comput., 22, 1905-1925, (2001) · Zbl 0986.65033
[40] G. Mei, A new method for solving the algebraic Riccati equation, Master’s thesis, Nanjing Aeronautical Institute, Campus P.O. Box 245, Nanjing, P.R. China, 1986.
[41] Paige, C.; Van Loan, C., A Schur decomposition for Hamiltonian matrices, Linear algebra appl., 41, 11-32, (1981) · Zbl 1115.15316
[42] Pester, C., Hamiltonian eigenvalue symmetry for quadratic operator eigenvalue problems, J. integral equations appl., 17, 1, 71-89, (2005) · Zbl 1088.35042
[43] Scuseria, G.; Henderson, T.; Sorensen, D., The ground state correlation energy of the random phase approximation from a ring coupled cluster doubles approach, J. chem. phys., 129, 23, 231101-1-231101-4, (2008)
[44] Sima, V., Algorithms for linear-quadratic optimization, Pure and applied mathematics, vol. 200, (1996), Marcel Dekker Inc. New York, NY · Zbl 0863.65038
[45] Sontag, E., Mathematical control theory, (1998), Springer-Verlag New York, NY
[46] Sorensen, D., Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. matrix anal. appl., 13, 1, 357-385, (1992) · Zbl 0763.65025
[47] D. Sorensen, Deflation for implicitly restarted Arnoldi methods, Technical report, Department of Computational and Applied Mathematics, Rice University, Houston, TX, 1998.
[48] Sorensen, D., Numerical methods for large eigenvalue problems, Acta numer., 519-584, (2002) · Zbl 1105.65325
[49] Sorensen, D., Passivity preserving model reduction via interpolation of spectral zeros, Systems control lett., 54, 347-360, (2005) · Zbl 1129.93340
[50] Stewart, G., A krylov – schur algorithm for large eigenproblems, SIAM J. matrix anal. appl., 23, 3, 601-614, (2001) · Zbl 1003.65045
[51] Stewart, G., Matrix algorithms, Eigensystems, vol. II, (2001), SIAM Philadelphia, USA · Zbl 0984.65031
[52] M. Stoll, Locking und Purging für den Hamiltonischen Lanczos-Prozess, Diplomarbeit, TU Chemnitz, Fakultät für Mathematik, Germany, 2005.
[53] Tisseur, F.; Meerbergen, K., The quadratic eigenvalue problem, SIAM rev., 43, 235-286, (2001) · Zbl 0985.65028
[54] Tretiak, S.; Isborn, C.; Niklasson, A.; Challacombe, M., Representation independent algorithms for molecular response calculations in time-dependent self-consistent field theories, J. chem. phys., 130, 5, 054111-1-054111-16, (2009)
[55] Watkins, D., On Hamiltonian and symplectic Lanczos processes, Linear algebra appl., 385, 23-45, (2004) · Zbl 1062.65047
[56] Watkins, D.S., The matrix eigenvalue problem: GR and Krylov subspace methods, (2007), Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 1142.65038
[57] N. Wong, V. Balakrishnan, C.-K. Koh, Passivity-preserving model reduction via a computationally efficient project-and-balance scheme, in: Proceedings of the Design Automation Conference, San Diego, CA, June 2004, pp. 369-374.
[58] Zhou, K.; Doyle, J.; Glover, K., Robust and optimal control, (1996), Prentice-Hall Upper Saddle River, NJ
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.