efficient computation of eigenvalues and eigenvectors for large matrices

Kolossváry István

BIOKOL Research LLC and

Budapest University of Technology and Economics, Department of Chemical Information

H-1111 Budapest Szt. Gellért tér 4; E-mail: Istvan@Kolossvary.hu

In this introduction to Krylov subspace projection methods, the conceptual framework used for the efficient computation of a few eigenvalues and eigenvectors of large matrices is outlined. The fundamental advantage of iterative methods derived from the well-known power iteration technique is that there is no direct reference to the matrix itself, only to its product with a series of vectors. Such matrix-vector products can be calculated in many cases in O(N) rather than O(N²) operations, which is a basic requirement for large-scale eigensystem calculations. It has been shown that the so-called Krylov subspace, which is spanned by a succession of vectors generated during consecutive power iterations holds information about a multitude of eigenvectors, not only the one associated with the largest magnitude eigenvalue. A combination of subspace iteration, inverse iteration, the Rayleigh-Ritz procedure, the renowned Arnoldi-Lánczos algorithm, and the use of standard LAPACK library functions together give rise to a set of powerful tools for solving large-scale eigenproblems, embodied among others in the public domain ARPACK package. An application to ARPACK for simulating protein domain motion is also presented.