Accelerating convergence by augmented Rayleigh-Ritz projections for large-scale eigenpair computation. (English) Zbl 1365.65096
Summary: Iterative algorithms for large-scale eigenpair computation of symmetric matrices are mostly based on subspace projections consisting of two main steps: a subspace update (SU) step that generates bases for approximate eigenspaces, followed by a Rayleigh-Ritz projection step that extracts approximate eigenpairs. A predominant methodology for the SU step makes use of Krylov subspaces and builds orthonormal bases piece by piece in a sequential manner. On the other hand, block methods such as the classic (simultaneous) subspace iteration, allow higher levels of concurrency than what is reachable by Krylov subspace methods, but may suffer from slow convergence. In this work, we analyze the rate of convergence for a simple block algorithmic framework that combines an augmented Rayleigh-Ritz (ARR) procedure with the subspace iteration. Our main results are Theorem 4.5 and its corollaries, which show that the ARR procedure can provide significant accelerations to convergence speed. Our analysis will offer useful guidelines for designing and implementing practical algorithms from this framework.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
Keywords:
extreme eigenpairs; power method; Rayleigh-Ritz procedure; iterative algorithm; large-scale eigenpair computation; symmetric matrices; Krylov subspace; convergenceReferences:
| [1] | Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, {\it Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide}, {\it Software Environ. Tools}, SIAM, Philadelphia, 2000. · Zbl 0965.65058 |
| [2] | M. Bollhöfer and Y. Notay, {\it JADAMILU: A software code for computing selected eigenvalues of large sparse symmetric matrices}, Comput. Phys. Comm., 177 (2007), pp. 951-964. · Zbl 1196.65072 |
| [3] | J. Cullum and W. Donath, {\it A block Lanczos algorithm for computing the q algebraically largest eigenvalues and a corresponding eigenspace of large, sparse, real symmetric matrices}, in Proceedings of the IEEE Conference on Decision and Control Including the 13th Symposium on Adaptive Processes, 1974, pp. 505-509. |
| [4] | J. W. Demmel, {\it Applied Numerical Linear Algebra}, SIAM, Philadelphia, 1997. · Zbl 0879.65017 |
| [5] | G. H. Golub and R. Underwood, {\it The block Lanczos method for computing eigenvalues}, in Mathematical Software, Vol.3, Academic Press, New York, 1977, pp. 361-377. · Zbl 0407.68040 |
| [6] | G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, 3rd ed., Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009 |
| [7] | R. G. Grimes, J. G. Lewis, and H. D. Simon, {\it A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems}, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 228-272. · Zbl 0803.65044 |
| [8] | A. V. Knyazev, {\it Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method}, SIAM J. Sci. Comput., 23 (2001), pp. 517-541. · Zbl 0992.65028 |
| [9] | C. Lanczos, {\it An iteration method for the solution of the eigenvalue problem of linear differential and integral operators}, J. Res. Natl. Bur. Std., 45 (1950), pp. 225-282. |
| [10] | R. M. Larsen, {\it Lanczos Bidiagonalization with Partial Reorthogonalization}, Technical report DAIMI PB-357, Aarhus University, 1998. |
| [11] | R. B. Lehoucq, {\it Implicitly restarted Arnoldi methods and subspace iteration}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 551-562. · Zbl 1004.65044 |
| [12] | R. B. Lehoucq, D. C. Sorensen, and C. Yang, {\it ARPACK users’ guide: Solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods}, Software Environ. Tools 6, SIAM, Philadelphia, 1998. · Zbl 0901.65021 |
| [13] | R.-C. Li and L.-H. Zhang, {\it Convergence of the block lanczos method for eigenvalue clusters}, Numer. Math., 131 (2015), pp. 83-113. · Zbl 1334.65073 |
| [14] | X. Liu, Z. Wen, and Y. Zhang, {\it Limited memory block krylov subspace optimization for computing dominant singular value decompositions}, SIAM J. Sci. Comput., 35 (2013), pp. A1641-A1668. · Zbl 1278.65045 |
| [15] | B. Parlett, {\it The Symmetric Eigenvalue Problem}, Prentice-Hall, Englewood Cliffs, NJ, 1980. · Zbl 0431.65017 |
| [16] | H. Rutishauser, {\it Computational aspects of F. L. Bauer’s simultaneous iteration method}, Numer. Math., 13 (1969), pp. 4-13. · Zbl 0182.21304 |
| [17] | H. Rutishauser, {\it Simultaneous iteration method for symmetric matrices}, Numer. Math., 16 (1970), pp. 205-223. · Zbl 0239.65037 |
| [18] | Y. Saad, {\it On the rates of convergence of the lanczos and the block-lanczos methods}, SIAM J. Numer. Anal., 17 (1980), pp. 687-706. · Zbl 0456.65016 |
| [19] | Y. Saad, {\it Numerical Methods for Large Eigenvalue Problems}, Manchester University Press, Manchester, UK, 1992. · Zbl 0991.65039 |
| [20] | D. C. Sorensen, {\it Implicitly restarted Arnoldi/Lanczos methods for large scale eigenvalue calculations}, in Parallel Numerical Algorithms (Hampton, VA, 1994), ICASE/LaRC Interdiscip. Ser. Sci. Eng. 4, Kluwer, Dordrecht, the Netherlands, 1996, pp. 119-165. · Zbl 0865.65019 |
| [21] | A. Stathopoulos and C. F. Fischer, {\it A Davidson program for finding a few selected extreme eigenpairs of a large, sparse, real, symmetric matrix}, Comput. Phys. Commun., 79 (1994), pp. 268-290. · Zbl 0878.65029 |
| [22] | G. W. Stewart, {\it Simultaneous iteration for computing invariant subspaces of non-Hermitian matrices}, Numer. Math., 25 (1975/76), pp. 123-136. · Zbl 0328.65025 |
| [23] | G. W. Stewart, {\it Matrix Algorithms Vol. {\it II}: Eigensystems}, SIAM, Philadelphia, 2001. · Zbl 0984.65031 |
| [24] | W. J. Stewart and A. Jennings, {\it A simultaneous iteration algorithm for real matrices}, ACM Trans. Math. Software, 7 (1981), pp. 184-198. · Zbl 0455.65028 |
| [25] | Z. Wen and Y. Zhang, {\it Block Algorithms with Augmented Rayleigh-Ritz Projections for Large-Scale Eigenpair Computation}, , 2015. · Zbl 1365.65096 |
| [26] | Q. Ye, {\it An adaptive block lanczos algorithm}, Numer. Algorithms, 12 (1996), pp. 97-110. · Zbl 0859.65032 |
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.
