×

Augmented block Householder Arnoldi method. (English) Zbl 1153.65034

Summary: Computing the eigenvalues and eigenvectors of a large sparse nonsymmetric matrix arises in many applications and can be a very computationally challenging problem. In this paper we propose the augmented block Householder Arnoldi method that combines the advantages of a block routine with an augmented Krylov routine. A public domain MATLAB code ahbeigs has been developed and numerical experiments indicate that the code is competitive with other publicly available codes.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Anderson, E.; Bai, Z.; Bischof, C.; Blackford, S.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; Sorensen, D., LAPACK users’ guide, (1999), SIAM Philadelphia, PA · Zbl 0934.65030
[2] Arnoldi, W.E., The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. appl. math., 9, 17-29, (1951) · Zbl 0042.12801
[3] Bai, Z.; Day, D.; Ye, Q., ABLE: an adaptive block Lanczos method for non-Hermitian eigenvalue problems, SIAM J. matrix anal. appl., 20, 1060-1082, (1999) · Zbl 0932.65045
[4] Bai, Z.; Demmel, J., On swapping diagonal blocks in real Schur form, Linear algebra appl., 186, 73-95, (1993) · Zbl 0783.65030
[5] Baglama, J., Dealing with linear dependence during the iterations of the restarted block Lanczos methods, Numer. algs., 25, 23-36, (2000) · Zbl 1012.65032
[6] Baglama, J.; Calvetti, D.; Reichel, L., Fast Leja points, Electron. trans. numer. anal., 7, 124-140, (1998) · Zbl 0912.65004
[7] Baglama, J.; Calvetti, D.; Reichel, L.; Ruttan, A., Computation of a few small eigenvalues of a large matrix with applications to liquid crystal modeling, J. comput. phys., 146, 203-226, (1998) · Zbl 0922.65026
[8] Baglama, J.; Calvetti, D.; Reichel, L., IRBL: an implicitly restarted block Lanczos method for large-scale Hermitian eigenproblems, SIAM J. sci. comput., 29, 5, 1650-1677, (2003) · Zbl 1044.65027
[9] Baglama, J.; Calvetti, D.; Reichel, L., : A MATLAB program for computing a few eigenpairs of a large sparse Hermitian matrix, Toms, 29, 5, 337-348, (2003) · Zbl 1070.65529
[10] Baglama, J.; Reichel, L., Augmented implicitly restarted Lanczos bidiagonalization methods, SIAM J. sci. comput., 27, 19-42, (2005) · Zbl 1087.65039
[11] Baglama, J.; Reichel, L., Restarted block Lanczos bidiagonalization methods, Numerical algorithms, 43, 251-272, (2006) · Zbl 1110.65027
[12] Zhaojun Bai, David Day, James Demmel, Jack Dongarra, A test matrix collection for non-Hermitian eigenvalue problems, release 1.0, September 1996.
[13] C. Bischof, Y. Sun, On orthogonal block elimination, Technical Report MCS-P441-0594, Mathematics and Computer Science Division, Argonne National Laboratory, 1994.
[14] Demmel, J.W., Applied numerical linear algebra, (1997), SIAM Philadelphia, PA · Zbl 0879.65017
[15] Dongarra, J.J.; DuCroz, J.; Duff, I.S.; Hammarling, S., A set of level 3 basic linear algebra subprograms, ACM trans. math. software, 16, 1-17, (1990) · Zbl 0900.65115
[16] I.S. Duff, R.G. Grimes, J.G. Lewis, User’s Guide for the Harwell-Boeing sparse matrix collection (Release I), Technical Report TR/PA/92/86, CERFACS, Toulouse, France, 1992. Matrices available at <http://math.nist.bov/MatrixMarket/>.
[17] Ericsson, T.; Ruhe, A., The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. comput., 35, 1251-1268, (1980) · Zbl 0468.65021
[18] Fokkema, D.R.; Sleijpen, G.L.G.; van der Vorst, H.A., Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils, SIAM J. sci. comput., 20, 94-125, (1998) · Zbl 0924.65027
[19] Golub, G.H.; Ye, Q., An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. sci. comput., 24, 312-334, (2002) · Zbl 1016.65017
[20] Grimes, R.G.; Lewis, J.L.; Simon, H.D., A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems, SIAM J. matrix anal., 15, 228-272, (1994) · Zbl 0803.65044
[21] Gu, G.; Cao, Z., A block GMRES method augmented with eigenvectors, Appl. math. comput., 121, 271-289, (2001) · Zbl 1024.65031
[22] Jia, Z., A refined iterative algorithm based on the block Arnoldi process for large unsymmetric eigenproblems, Linear algebra appl., 270, 171-189, (1998) · Zbl 0896.65035
[23] Jia, Z., Polynomial characterizations of the approximate eigenvectors by the refined Arnoldi method and an implicitly restarted refined Arnoldi algorithm, Linear algebra appl., 287, 191-214, (1998) · Zbl 0939.65056
[24] Lehoucq, R.B., Implicitly restarted Arnoldi methods and subspace iteration, SIAM J. matrix anal. appl., 23, 551-562, (2001) · Zbl 1004.65044
[25] R.B. Lehoucq, K.J. Maschhoff, Implementation of an implicitly restarted block Arnoldi method, Preprint MCS-P649-0297, Argonne National Laboratory, Argonne, IL, 1997.
[26] R.B. Lehoucq, J.A. Scott, An evaluation of software for computing eigenvalues of sparse nonsymmetric matrices, Technical report MCS-P547-1195, Argonne National Laboratory, 1995.
[27] Lehoucq, R.B.; Sorensen, D.C., Deflation techniques for an implicitly restarted Arnoldi iteration, SIAM J. matrix anal. appl., 17, 789-821, (1996) · Zbl 0863.65016
[28] R.B. Lehoucq, K. Maschhoff, D.C. Sorensen, and C. Yang, ARPACK, http://www.caam.rice.edu/software/ARPACK/ (1998).
[29] Lehoucq, R.B.; Sorensen, D.C.; Yang, C., ARPACK users’ guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods, (1998), SIAM Publications Philadelphia · Zbl 0901.65021
[30] O.A. Marques, BLZPACK: A Fortran 77 implementation of the block Lanczos algorithm. Code available from: <http://www.nersc.gov/ osni/marques-software.html>.
[31] The MathWorks, MATLAB Application Program Interface Guide, Version 5, The MathWorks, Inc., Natick, 1998.
[32] K. Meerbergen, J. Scott, The design of a block rational Lanczos code with partial reorthogonalization and implicit restarting, Technical Report RAL-TR-2000-011, 2000.
[33] J. Möller, Implementations of the Implicitly Restarted Block Arnoldi Method, Technical report, Royal Institute of Technology (KTH), Department of Numerical Analysis and Computer Science, TRITA-NA-0446, 2004.
[34] Morgan, R., On restarting the Arnoldi method for large nonsymmetric eigenvalue problems, Math. comput., 65, 1213-1230, (1996) · Zbl 0857.65041
[35] Morgan, R., Computing interior eigenvalues of large matrices, Linear algebra appl., 154-156, 289-309, (1991) · Zbl 0734.65029
[36] R. Morgan, GMRES with Deflated Restarting, Technical Report, 2001. · Zbl 1018.65042
[37] Morgan, R., Restarted block GMRES with deflation of eigenvalues, Appl. numer. math., 54, 222-236, (2005) · Zbl 1074.65043
[38] Morgan, R.; Zeng, M., Harmonic projection methods for large non-symmetric eigenvalue problems, Numer. linear algebra appl., 5, 33-55, (1998) · Zbl 0937.65045
[39] Saad, Y., Numerical methods for large eigenvalue problems, (1992), Halsted Press New York · Zbl 0991.65039
[40] Saad, Y., Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems, Math. comput., 42, 166, 567-588, (1984) · Zbl 0539.65013
[41] Schreiber, R.; Van Loan, C., A storage-efficient WY representation for products of Householder transformations, SIAM J. sci. stat. comput., 10, 53-57, (1989) · Zbl 0664.65025
[42] Scott, J.A., An Arnoldi code for computing selected eigenvalues of sparse real unsymmetric matrices, ACM trans. math. software, 21, 432-475, (1995) · Zbl 0888.65041
[43] D.S. Scott, LASO2 - FORTRAN implementation of the Lanczos process with selective orthogonalization, Code and documentation available from Netlib.
[44] Sorensen, D.C., Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. matrix anal. appl., 13, 357-385, (1992) · Zbl 0763.65025
[45] A. Stathopoulos, Locking issues for finding a large number of eigenvectors of hermitian matrices, Tech Report: WM-CS-2005-09, July, 2005, Revised June 2006.
[46] Stewart, G.W., A krylov – schur algorithm for large eigenproblems, SIAM J. matrix anal. appl., 23, 3, 601-614, (2001) · Zbl 1003.65045
[47] Stoer, J.; Bulirsch, R., Introduction to numerical analysis, (1993), Springer New York · Zbl 0771.65002
[48] Sun, X.; Bischof, C.A., Basis-kernel representation of orthogonal matrices, Simax, 16, 4, 1184-1196, (1995) · Zbl 0837.15010
[49] Walker, H., Implementation of the GMRES method using Householder transformations, SIAM J. sci. comput., 9, 152-163, (1988) · Zbl 0698.65021
[50] Wu, K.; Simon, H., Thick-restart Lanczos method for large symmetric eigenvalue problems, SIAM. J. matrix anal. appl., 22, 602-616, (2001) · Zbl 0969.65030
[51] Y. Zhou, Y. Saad, Block Krylov-Schur method for large symmetric eigenvalue problems, Technical report Department of Computer Science and Engineering, University of Minnesota, 2004.
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.