A MULTIPROCESSOR ALGORITHM FOR THE SYMMETRIC TRIDIAGONAL EIGENVALUE PROBLEM*
Sy-Shin Lo, Bernard Philippe, Ahmed Sameh · 2015
Abstract. A multiprocessor algorithm for finding few or all eigenvalues and the corresponding eigenvec-tors of a symmetric tridiagonal matrix is presented. It is a pipelined variation of EISPACK routinesmBISECT and TINVIT which consists ofthe three steps: isolation, extraction-inverse iteration, and partial orthogonaliz-ation. Multisections are performed for isolating the eigenvalues in a given interval, while bisection or the Zeroin method is used to extract these isolated eigenvalues. After the corresponding eigenvectors have been computed by inverse iteration, the modified Gram-Schmidt method is used to orthogonalize certain groups of these vectors. Experiments on the Alliant FX/8 and CRAY X-MP/48 multiprocessors show that this algorithm achieves high speed-up over BISECT and TINVIT; in fact it is much faster than TQL2 when all the eigenvalues and eigenvectors are required. Key words, eigenvalues, multiprocessors, tridiagonal matrices AMS(MOS) subject classification. 65F15