ABSTRACT
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 5.2 The Real Symmetric Eigenvalue Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 5.3 Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 5.4 The Power Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 5.5 Subspace Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 5.6 The Lanczos Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 5.7 Restarted Lanczos Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.7.1 Explicitly Restarted Lanczos Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 5.7.2 Implicitly Restarted Lanczos Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
5.8 The Jacobi-Davidson Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 5.9 The Unsymmetric Eigenproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.10 Parallel Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.10.1 Matrix-Vector Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 5.10.2 Vector Orthonormalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 5.10.3 Eigensolution of Small Dense Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 5.10.4 Solution of Linear Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.11 Iterative Methods and Parallel Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 5.11.1 Classical Lanczos Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 5.11.2 Unbounded Explicitly Restarted and Implicitly Restarted Lanczos Methods . . 186 5.11.3 Fixed Length Run Explicitly Restarted and Implicitly Restarted
Lanczos Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 5.12 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
The problem of computing a subset of the eigenvalues and corresponding eigenvectors of large, often sparse, symmetric matrices is addressed. The only tractable methods for solving this problem are iterative in nature. In these the matrix of interest is used only as a multiplier, thereby allowing its sparsity to be preserved. Two main approaches are discussed — subspace iteration methods and Krylov space-based methods. The fundamental operations employed in both approaches — matrix-
vector products, vector orthogonalization, etc., are amenable to efficient parallel implementation on a wide range of machine architectures. Several variants of the iterative algorithms, designed to improve computational efficiency and reduce storage demands, are discussed. The parallel implementation of the basic operations is addressed. The performances of the methods on machines having different architectures is illustrated by their application to a number of matrices selected from standard library collections. The experiments show that the choice of the best parallel method to use is significantly influenced by the nature of the machine on which it is to be executed. The natural extension of the methods to the solution of the unsymmetric problem is briefly discussed. A short overview of the extensive literature devoted to computational aspects of solving eigenproblems is given.
