A restarted Lanczos process for computing a large percentage of the eigenvalues of a symmetric matrix

[摘要] The Lanczos algorithm is a well known technique for approximating a few eigenvalues and corresponding eigenvectors of a large-scale real symmetric matric arising in many scientific and engineering applications. In this thesis a modified restarted k-step Lanczos algorithm is presented. The basic Lanczos process suffers from numerical difficulties such as large storage requirements and loss of orthogonality among the basis vectors. The current restarted Lanczos method is designed to overcome these difficulties by fixing the number of steps in the Lanczos process at a prespecified value k, where k is modest and proportional to the total number of eigenvalues of interest. However, it is possible that the total number of desired eigenvalues may not be moderate. The main difference between this restart scheme and other existing schemes is that the prescribed value k in our algorithm is only a reasonable number. It is independent of the total number of desired eigenvalues. In other words, this algorithm may compute a large percentage of eigenvalues and associated eigenvectors of a large symmetric matrix with significantly reduced storage requirement. Strategies for implementing the algorithm on parallel distributed-memory machines are presented. The efficiency of this algorithm is justified by computational results for the electronic structure problem in quantum chemistry.

[发布机构] Rice University