The improved unsymmetric Lanczos process on massively distributed memory computers

For the eigenvalues of a large and sparse unsymmetric coefficient matrix, we propose an improved version of the unsymmetric Lanczos process combining elements of numerical stability and parallel algorithm design. Stability is obtained by a coupled two-term recurrences procedure that generates Lanczos vectors scaled to unit length. The algorithm is derived such that all inner products and matrix-vector multiplications of a single iteration step are independent and communication time required for inner product can be overlapped efficiently with computation time. Therefore, the cost of global communication on parallel distributed memory computers can be significantly reduced. The resulting algorithm maintains the favorable properties of the Lanczos process while not increasing computational costs. In this paper, a simple theoretical model of computation and communications phases is presented to allow us to give a qualitative analysis of the parallel performance with two-dimensional grid topology. The theoretical results in the performance is demonstrated by experimental timing results from finite element models carried out on massively parallel distributed memory computer Parsytec GC/PowerPlus.