×

Preserving geometric properties of the exponential matrix by block Krylov subspace methods. (English) Zbl 1107.65039

Given a large square real matrix \(A\) and a rectangular tall matrix \(Q,\) many application problems require the approximation of the operation \(\exp (A)Q\). The authors show that an appropiate use of the block Lanczos method allows one to obtain a structure preserving approximation to \(\exp (A)Q\) when \(A\) is skew-symmetric or skew-symmetric and Hamiltonan. Moreover, for \(A\) Hamiltonian the authors derive a new variant of the block Lanczos method that again preserves the geometric properties of the exact scheme. Numerical results are also provided.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F10 Iterative numerical methods for linear systems

Software:

ABLE; Matlab; JDQZ; JDQR; QMRPACK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P.-A. Absil, R. Mahony, and R. Sepulchre, Continuous-time subspace flows related to the symmetric eigenproblem, tech. rep. FSU-CSIT-04-23, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, February 2004.
[2] J. I. Aliaga, D. L. Boley, R. W. Freund, and V. Hernàndez, A Lanczos-type method for multiple starting vectors, Math. Comput., 69 (2000), pp. 1577–1601. · Zbl 0953.65018
[3] Z. Bai, D. Day, and Q. Ye, ABLE: an adaptive block Lanczos method for non-Hermitian eigenvalue problems, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 1060–1082. · Zbl 0932.65045 · doi:10.1137/S0895479897317806
[4] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[5] Z. Bai and R. W. Freund, A symmetric band Lanczos process based on coupled recurrences and some applications, SIAM J. Sci. Comput., 23 (2001), pp. 542–562. · Zbl 0997.65064 · doi:10.1137/S1064827500371773
[6] A. Baker, Matrix groups. An Introduction to Lie Group Theory, Springer Undergraduate Mathematics Series, Springer, London, 2002. · Zbl 1009.22001
[7] P. Benner and H. Fassbender, An implicitly restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem, Linear Algebra Appl., 263 (1997), pp. 75–111. · Zbl 0884.65028 · doi:10.1016/S0024-3795(96)00524-1
[8] P. Benner and H. Fassbender, An implicitly restarted symplectic Lanczos method for the symplectic eigenvalue problem, SIAM J. Matrix Anal. Appl., 22 (2000), pp. 682–713. · Zbl 0985.65026 · doi:10.1137/S0895479898343115
[9] P. Benner, D. Kressner, and V. Mehrmann, Structure preservation: a challenge in computational control, Future Gener. Comput. Sys., 19 (2003), pp. 1243–1252. · doi:10.1016/S0167-739X(03)00049-9
[10] T. J. Bridges and S. Reich, Computing Lyapunov exponents on a Stiefel manifold, Physica D, 156 (2001), pp. 219–238. · Zbl 0979.37044 · doi:10.1016/S0167-2789(01)00283-4
[11] E. Celledoni and A. Iserles, Approximating the exponential from a Lie algebra to a Lie group, Math. Comput., 69 (2000), pp. 1457–1480. · Zbl 0956.65009 · doi:10.1090/S0025-5718-00-01223-0
[12] E. Celledoni and A. Iserles, Methods for the approximation of the matrix exponential in a Lie-algebraic setting, IMA J. Numer. Anal., 21 (2001), pp. 463–488. · Zbl 1009.65040 · doi:10.1093/imanum/21.2.463
[13] E. Celledoni and I. Moret, A Krylov projection method for systems of ODEs, Appl. Numer. Math., 24 (1997), pp. 365–378. · Zbl 0885.65073 · doi:10.1016/S0168-9274(97)00033-0
[14] E. Celledoni and B. Owren, A class of intrinsic schemes for orthogonal integration, SIAM J. Numer. Anal., 40 (2002), pp. 2069–2084. · Zbl 1034.65054 · doi:10.1137/S0036142901385143
[15] E. Celledoni and B. Owren, On the implementation of Lie group methods on the Stiefel manifold, Numer. Algorithms, 32 (2003), pp. 163–183. · Zbl 1029.65072 · doi:10.1023/A:1024079724094
[16] N. del Buono, L. Lopez, and R. Peluso, Computation of exponentials of large sparse skew symmetric matrices, SIAM J. Sci. Comput., 27 (2005), pp. 278–293. · Zbl 1108.65037 · doi:10.1137/030600758
[17] L. Dieci and E. S. Van Vleck, Computation of a few Lyapunov exponents for continuous and discrete dynamical systems, Appl. Numer. Math., 17 (1995), pp. 275–291. · Zbl 0834.65069 · doi:10.1016/0168-9274(95)00033-Q
[18] F. Diele, L. Lopez, and R. Peluso, The Cayley transform in the numerical solution of unitary differential systems, Adv. Comput. Math., 8 (1998), pp. 317–334. · Zbl 0904.65069 · doi:10.1023/A:1018908700358
[19] V. Druskin and L. Knizhnerman, Krylov subspace approximation of eigenpairs and matrix functions in exact and computer arithmetic, Numer. Linear Algebra Appl., 2 (1995), pp. 205–217. · Zbl 0831.65042 · doi:10.1002/nla.1680020303
[20] A. Edelman, T. Arias, and S. T. Smith, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 303–353. · Zbl 0928.65050 · doi:10.1137/S0895479895290954
[21] T. Eirola, Krylov integrators for Hamiltonian problems, October 20–23, 2004. Talk presented at Workshop on Exponential Integrators, Innsbruck, Austria, see http://techmath.uibk.ac.at/numbau/alex/events/conference2004.html.
[22] S. Fiori, A theory for learning by weight flow on Stiefel–Grassman manifold, Neural Comput., 13 (2001), pp. 1625–1647. · Zbl 0982.68111 · doi:10.1162/089976601750265036
[23] R. W. Freund and N. M. Nachtigal, Software for simplified Lanczos and QMR algorithms, Appl. Numer. Math., 19 (1995), pp. 319–341. · Zbl 0853.65041 · doi:10.1016/0168-9274(95)00089-5
[24] R. Friesner, L. Tuckerman, B. Dornblaser, and T. Russo, A method for exponential propagation of large systems of stiff nonlinear differential equations, SIAM J. Sci. Comput., 4 (1989), pp. 327–354.
[25] E. Gallopoulos and Y. Saad, Efficient solution of parabolic equations by Krylov approximation methods, SIAM J. Sci. Stat. Comput., 13 (1992), pp. 1236–1264. · Zbl 0757.65101 · doi:10.1137/0913071
[26] R. Grimes, J. Lewis, and H. Simon, A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 228–272. · Zbl 0803.65044 · doi:10.1137/S0895479888151111
[27] E. Hairer, C. Lubich, and G. Wanner, Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations, vol. 31 of Springer Series in Computational Mathematics, Springer, Berlin, 2002. · Zbl 0994.65135
[28] M. Hochbruck and C. Lubich, On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 34 (1997), pp. 1911–1925. · Zbl 0888.65032 · doi:10.1137/S0036142995280572
[29] M. Hochbruck and C. Lubich, Exponential integrators for quantum-classical molecular dynamics, BIT, 39 (1999), pp. 620–645. · Zbl 0985.81002 · doi:10.1023/A:1022335122807
[30] M. Hochbruck, C. Lubich, and H. Selhofer, Exponential integrators for large systems of differential equations, SIAM J. Sci. Comput., 19 (1998), pp. 1552–1574. · Zbl 0912.65058 · doi:10.1137/S1064827595295337
[31] A. Iserles, On Cayley-transform methods for the discretization of Lie-group equations, Found. Comput. Math., 1 (2001), pp. 129–160. · Zbl 1014.65060 · doi:10.1007/s102080010003
[32] A. Iserles and A. Zanna, Efficient computation of the matrix exponential by generalized polar decompositions, SIAM J. Numer. Anal., 42 (2005), pp. 2218–2256. · Zbl 1084.65040 · doi:10.1137/S0036142902415936
[33] M. Karow, D. Kressner, and F. Tisseur, Structured eigenvalue condition numbers, tech. rep. NA - 467, University of Manchester, April 2005. To appear in SIAM J. Matrix Anal. Appl.
[34] B. J. Leimkuhler and E. S. Van Vleck, Orthosymplectic integration of linear Hamiltonian systems, Numer. Math., 77 (1997), pp. 269–282. · Zbl 0880.65053 · doi:10.1007/s002110050286
[35] L. Lopez and V. Simoncini, Analysis of projection methods for rational function approximation to the matrix exponential, SIAM J. Numer. Anal., 44 (2006), pp. 613–635. · Zbl 1158.65031 · doi:10.1137/05062590
[36] The MathWorks, Inc., MATLAB 7, September 2004.
[37] C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev., 45 (2003), pp. 3–49. · Zbl 1030.65029 · doi:10.1137/S00361445024180
[38] A. Nauts and R. Wyatt, New approach to many state quantum dynamics: the recursive residue generation method, Phys. Rev. Lett., 51 (1983), pp. 2238–2241. · doi:10.1103/PhysRevLett.51.2238
[39] P. Nettesheim and C. Schütte, Numerical integrators for quantum-classical molecular dynamics, in Computational Molecular Dynamics: Challenges, Methods, Ideas, P. Deuflhard, J. Hermans, B. Leimkuhler, A. E. Marks, S. Reich, and R. D. Skeel, eds., vol. 4 of Lecture Notes in Computational Science and Engineering, Springer, Berlin–New York, 1999, pp. 396–411. · Zbl 0966.81064
[40] T. Park and J. Light, Unitary quantum time evolution by iterative Lanczos reduction, J. Chem. Phys., 85 (1986), pp. 5870–5876. · doi:10.1063/1.451548
[41] I. Puzynin, A. Selin, and S. Vinitsky, Magnus-factorized method for numerical solving the time-dependent Schrödinger equation, Comput. Phys. Commun., 126 (2000), pp. 158–161. · Zbl 0962.65103 · doi:10.1016/S0010-4655(99)00225-8
[42] Y. Saad, Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 29 (1992), pp. 209–228. · Zbl 0749.65030 · doi:10.1137/0729014
[43] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Society for Industrial and Applied Mathematics, Philadelphia, 2003. · Zbl 1031.65046
[44] A. Salam, On theoretical and numerical aspects of symplectic Gram–Schmidt-like algorithms, Numer. Algorithms, 39 (2005), pp. 437–462. · Zbl 1111.65038 · doi:10.1007/s11075-005-0963-2
[45] A. Salam and A. Bouhamidi, A structure-preserving Krylov subspace method for large sparse Hamiltonian matrix eigenvalue problem, tech. rep., Laboratoire de Mathématiques Pures et Appliquées, Université du Littoral, Calais, France, 2005.
[46] D. Watkins, On Hamiltonian and symplectic Lanczos processes, Linear Algebra Appl., 385 (2004), pp. 23–45. · Zbl 1062.65047 · doi:10.1016/j.laa.2002.11.001
[47] A. Zanna and H. Z. Munthe-Kaas, Generalized polar decompositions for the approximation of the matrix exponential, SIAM J. Matrix Anal. Appl., 23 (2002), pp. 840–862. · Zbl 0999.65060 · doi:10.1137/S0895479800377551
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.