Abstract
It is well known that the Lanczos process suffers from loss of orthogonality in the case of finite-precision arithmetic. Several approaches have been proposed in order to address this issue, thus enabling the successful computation of approximate eigensolutions. However, these techniques have been studied mainly in the context of long Lanczos runs, but not for restarted Lanczos eigensolvers. Several variants of the explicitly restarted Lanczos algorithm employing different reorthogonalization strategies have been implemented in SLEPc, the Scalable Library for Eigenvalue Computations. The aim of this work is to assess the numerical robustness of the proposed implementations as well as to study the impact of reorthogonalization in parallel efficiency.
Topics: Numerical methods, parallel and distributed computing.
This work was supported in part by the Valencian Regional Administration, Directorate of Research and Technology Transfer, under grant number GV06/091.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Nat. Bur. Standards 45, 255–282 (1950)
Paige, C.C.: Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix. J. Inst. Math. Appl. 18(3), 341–349 (1976)
Sorensen, D.C.: Implicit application of polynomial filters in a k-step Arnoldi method. SIAM J. Matrix Anal. Appl. 13, 357–385 (1992)
Hernandez, V., Roman, J.E., Vidal, V.: SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems. ACM Trans. Math. Software 31(3), 351–362 (2005)
Grimes, R.G., Lewis, J.G., Simon, H.D.: A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems. SIAM J. Matrix Anal. Appl. 15(1), 228–272 (1994)
Parlett, B.N.: The Symmetric Eigenvalue Problem (Reissued with revisions by SIAM, Philadelphia, 1998). Prentice-Hall, Englewood Cliffs (1980)
Nour-Omid, B.: The Lanczos algorithm for solution of large generalized eigenproblem. In: Hughes, T.J.R. (ed.) The Finite Element Method, pp. 582–630. Prentice-Hall, Englewood Cliffs (1987)
Paige, C.C.: Computational variants of the Lanczos method for the eigenproblem. J. Inst. Math. Appl. 10, 373–381 (1972)
Paige, C.C.: Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem. Linear Algebra Appl. 34, 235–258 (1980)
Cullum, J.K., Willoughby, R.A.: Lanczos Algorithms for Large Symmetric Eigenvalue Computations, vol. 1: Theory (Reissued by SIAM, Philadelphia, 2002). Birkhaüser, Boston (1985)
Parlett, B.N., Scott, D.S.: The Lanczos algorithm with selective orthogonalization. Math. Comp. 33, 217–238 (1979)
Grcar, J.F.: Analyses of the Lanczos algorithm and of the approximation problem in Richardson’s method. Technical Report 1074, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois (1981)
Simon, H.D.: The Lanczos algorithm with partial reorthogonalization. Math. Comp. 42(165), 115–142 (1984)
Simon, H.D.: Analysis of the symmetric Lanczos algorithm with reorthogonalization methods. Linear Algebra Appl. 61, 101–132 (1984)
Hoffmann, W.: Iterative algorithms for Gram-Schmidt orthogonalization. Computing 41(4), 335–348 (1989)
Björck, Å.: Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics, Philadelphia (1996)
Kim, S.K., Chronopoulos, A.T.: A class of Lanczos-like algorithms implemented on parallel computers. Parallel Comput. 17(6–7), 763–778 (1991)
Hernandez, V., Roman, J.E., Tomas, A.: Parallel Arnoldi eigensolvers with enhanced scalability via global communications rearrangement. Submitted (2006)
Balay, S., et al.: PETSc users manual. Technical Report ANL-95/11 - Revision 2.3.1, Argonne National Laboratory (2006)
Szularz, M., Weston, J., Clint, M.: Explicitly restarted Lanczos algorithms in an MPP environment. Parallel Comput. 25(5), 613–631 (1999)
Cooper, A., Szularz, M., Weston, J.: External selective orthogonalization for the Lanczos algorithm in distributed memory environments. Parallel Comput. 27(7), 913–923 (2001)
Duff, I.S., Grimes, R.G., Lewis, J.G.: Sparse matrix test problems. ACM Trans. Math. Software 15(1), 1–14 (1989)
Davis, T.: University of Florida Sparse Matrix Collection. NA Digest (1992), Available at http://www.cise.ufl.edu/research/sparse/matrices
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Hernandez, V., Roman, J.E., Tomas, A. (2007). Evaluation of Several Variants of Explicitly Restarted Lanczos Eigensolvers and Their Parallel Implementations . In: Daydé, M., Palma, J.M.L.M., Coutinho, Á.L.G.A., Pacitti, E., Lopes, J.C. (eds) High Performance Computing for Computational Science - VECPAR 2006. VECPAR 2006. Lecture Notes in Computer Science, vol 4395. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71351-7_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-71351-7_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71350-0
Online ISBN: 978-3-540-71351-7
eBook Packages: Computer ScienceComputer Science (R0)