A CLASS OF LANCZOS-LIKE ALGORITHMS IMPLEMENTED ON PARALLEL COMPUTERS

The Lanczos algorithm is most commonly used in approximating a small number of extreme eigenvalues and eigenvectors for symmetric large sparse matrices. Main memory accesses for shared memory systems or global communications (synchronizations) in message passing systems decrease the computation speed. In this paper, the standard Lanczos algorithm is restructured so that only one synchronization point is required; that is, one global communication in a message passing distributed-memory machine or one global memory sweep in a shared-memory machine per each iteration is required. We also introduce the s-step Lanczos method for finding a few eigenvalues of symmetric large sparse matrices in a similar way to the s-step Conjugate Gradient method [2], and we prove that the s-step method generates reduction matrices which are similar to reduction matrices generated by the standard method. One iteration of the s-step Lanczos algorithm corresponds to s iterations of the standard Lanczos algorithm. The s-step method has improved data locality, minimized global communication and has superior parallel properties to the standard method. These algorithms are implemented on a 64-node NCUBE/seven hypercube and a CRAY-2, and performance results are presented.