×

Deflated block Krylov subspace methods for large scale eigenvalue problems. (English) Zbl 1191.65035

The aim of the paper is to study a class of deflated block Krylov subspace methods, for solving large scale matrix eigenvalue problems, techniques which are different from conventional block Krylov subspace methods in the way of generating the approximate subspaces.
The first section is of introductory nature.
The second section briefly recalls the concept of block Krylov subspace and related procedures for solving large scale eigenvalue problems, giving then a brief introduction of the deflated block Krylov subspace. The authors also present an Arnoldi-type algorithm which can accomplished the orthogonalization procedure presented above.
The third section deals with some deflated Krylov subspace methods for solving large scale eigenvalue problems; particularly, an Arnoldi-type method and its refined variant will be outlined and compared. The authors prove in this section that due to deflation, approximate subspaces constructed by the new method have similar properties to ones constructed by the implicitly restarted Arnoldi method, or the restarted Arnoldi methods augmented with approximate eigenvectors. The new methods preserve the superiorities of regular block Krylov subspace methods and regular Krylov subspace methods augmented with approximate eigenvectors.
In the fourth section, the authors present seven numerical examples computed by the Arnoldi-type method and its refined variant. These examples demonstrate the efficiency of the presented methods for computing partial or nearly clustered eigenvalues of large matrices. Also, the test results show that the refined variant can improve the performance of the Arnoldi-type method in computing partial eigenvalues of large matrices.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Bai, Z.; Demmel, J.; Dongarra, J.; Ruhe, A.; van der Vorst, H., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (2000), SIAM: SIAM Philadelphia) · Zbl 0965.65058
[2] Saad, Y., Numerical Methods for Large Eigenvalue Problems (1992), Manchester University Press: Manchester University Press UK · Zbl 0991.65039
[3] Stewart, G. W., Matrix Algorithms Volume II: Eigensystems (2001), SIAM: SIAM Philadelphia · Zbl 0984.65031
[4] Sleijpen, G. L.G.; Van der Vorst, H. A., A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17, 401-425 (1996) · Zbl 0860.65023
[5] Knyazev, A. V.; Skorokhodov, A. L., Preconditioned gradient-type iterative methods in a subspace for partial generalized symmetric eigenvalue problems, SIAM J. Numer. Anal., 31, 1226-1239 (1994) · Zbl 0812.65031
[6] Knyazev, A. V., Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23, 517-541 (2001) · Zbl 0992.65028
[9] Lehoucq, R. B.; Sorensen, D. C.; Yang, C., Arpack Users’ Guide: Solution of Large Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods (1998), SIAM: SIAM Philadelphia · Zbl 0901.65021
[10] 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
[11] Beattie, C. A.; Embree, M.; Rossi, J., Convergence of restarted Krylov subspace to invariant subspaces, SIAM J. Matrix Anal. Appl., 25, 1074-1109 (2004) · Zbl 1067.65037
[12] Beattie, C. A.; Embree, M.; Sorensen, D. C., Convergence of polynomial restarted Krylov methods for eigenvalue computations, SIAM Rev., 47, 492-515 (2005) · Zbl 1073.65028
[13] Jia, Z.; Stewart, G. W., An analysis of the Rayleigh-Ritz method for approximating eigenspaces, Math. Comp., 70, 637-647 (2001) · Zbl 0968.65020
[14] Kujlaars, A. B.J., Convergence analysis of Krylov subspace iterations with methods from potential theory, SIAM Rev., 48, 3-40 (2006) · Zbl 1092.65031
[15] Jia, Z., Generalized block Lanczos methods for large unsymmetric eigenproblems, Numer. Math., 80, 239-266 (1998) · Zbl 0910.65018
[16] Morgan, R. B., Restarted block GMRES with deflation of eigenvalues, Appl. Numer. Math., 54, 222-236 (2005) · Zbl 1074.65043
[17] Baglama, J.; Calvetti, D.; Reichel, L., irbleigs: A MATLAB program for computing a few eigenpairs of a large sparse Hermitian matrix, SIAM J. Sci. Comput., 24, 1650-1677 (2003) · Zbl 1044.65027
[18] Golub, G. H.; Underwood, R., A block Lanczos method for computing the singular values and corresponding singular vectors of a matrix, ACM Trans. Math. Softw., 7, 149-169 (1981) · Zbl 0466.65022
[19] Grimes, R.; Lewis, J.; Simon, H., A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems, SIAM J. Matrix Anal. Appl., 15, 228-272 (1994) · Zbl 0803.65044
[20] Zhou, Y. K.; Saad, Y., Block Krylov-Schur method for large symmetric eigenvalue problems, Numer. Algorithms, 47, 341-359 (2008) · Zbl 1153.65330
[21] Bai, Z.; Day, D.; Ye, Q., ABLE: An adaptive block Lanczos method for non-Hermitian eigenvalue problem, SIAM J. Matrix Anal. Appl., 20, 1060-1082 (1999) · Zbl 0932.65045
[22] Jia, Z., Refined iterative algorithms based on block Arnoldi process for large unsymmetric eigenproblems, Linear Algebra Appl., 270, 171-189 (1998) · Zbl 0896.65035
[23] Sadkane, M., Block-Arnoldi and Davidson methods for unsymmetric large eigenvalue problems, Numer. Math., 64, 195-211 (1993) · Zbl 0791.65021
[24] Scott, J. A., An Arnoldi code for computing selected eigenvalues of sparse, real, unsymmetric matrices, ACM Trans. Math. Softw., 214, 432-475 (1995) · Zbl 0888.65041
[25] Aliaga, J. I.; Boley, D. L.; Freund, R. W.; Hernandez, V., A Lanczos-type method for multiple starting vectors, Math. Comp., 69, 1577-1601 (2000) · Zbl 0953.65018
[26] Bai, Z.; Freund, R. W., A symmetric band Lanczos process based on coupled recurrences and some applications, SIAM J. Sci. Comput., 23, 542-562 (2001) · Zbl 0997.65064
[27] Freund, R. W., Krylov-subspace methods for reduced-order modeling in circuit simulation, J. Comput. Appl. Math., 123, 395-421 (2000) · Zbl 0964.65082
[28] Yin, Qian; Lu, Linzhang, An implicitly restarted block Arnoldi method in vector-wise fashion, Numer. Math. J. Chin. Univ., 15, 268-277 (2006) · Zbl 1132.65031
[29] Morgan, R. B., On restarting the Arnoldi method for large nonsymmetric eigenvalue problems, Math. Comp., 65, 1213-1230 (1996) · Zbl 0857.65041
[30] Gutknecht, M. H.; Schmelzer, T., The block grade of a block Krylov space, Linear Algebra Appl., 430, 174-185 (2009) · Zbl 1163.65015
[31] Gutknecht, M. H., Block Krylov space methods for linear systems with multiple right-hand sides: An introduction, (Siddiqi, A. H.; Duff, I. S.; Christensen, O., Modern Mathematical Models, Methods and Algorithms for Real World Systems (2007), Anamaya Publishers: Anamaya Publishers New Delhi, India), 420-447
[32] Arnoldi, W. E., The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9, 17-29 (1951) · Zbl 0042.12801
[33] Daniel, J. W.; Gragg, W. B.; Sterwart, G. W., Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. Comp., 30, 772-795 (1976) · Zbl 0345.65021
[34] Simon, H. D., The Lanczos algorithm with partial reorthogonalization, Math. Comp., 42, 115-136 (1984) · Zbl 0546.65017
[36] Duff, I. S.; Grimes, R. G.; Lewis, J. G., Sparse matrix test problems, ACM Trans. Math. Softw., 15, 1-14 (1989) · Zbl 0667.65040
[37] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1988), Oxford University Press · Zbl 0626.65029
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.