A SCALABLE EIGENVALUE SOLVER FOR SYMMETRICAL TRIDIAGONAL MATRICES

Both massively parallel computers and clusters of workstations are con sidered promising platforms for numerical scientific computing. This p aper describes the first distributed memory implementation of the spli t-merge algorithm, an eigenvalue solver for symmetric tridiagonal matr ices that uses Laguerre's iteration and exploits the separation proper ty in order to create independent subtasks. Implementations of the spl it-merge algorithm on both an nCUBE-2 hypercube and a cluster of Sun S parc-10 workstations are described, with emphasis on load balancing, c ommunication overhead, and interaction with other user processes. A pe rformance study demonstrates the advantage of the new algorithm over a parallelization of the well-known bisection algorithm. A comparison o f the performance of the nCUBE-2 and cluster implementations supports the claim that workstation clusters offer a cost-effective alternative to massively parallel computers for certain scientific applications.