CRPC-TR98749						February 1998

Title: Parallelizing the Divide and Conquer Algorithm for the Symmetric 
Tridagonal Eigenvalue Problem on Distributed Memory Architectures

Authors: Francoise Tisseur and Jack Dongarra

Submitted August 1998; Available as LAPACK Working Note 132

Abstract:
We present a new parallel implementation of a divide and conquer 
algorithm for computing the spectral decomposition of a symmetric 
tridiagonal matrix on distributed architectures.  The implementation we 
develop differs from other implementations in that we use a two 
dimensional block cyclic distribution of the data, we use the Lowner 
theorem approach to compute orthogonal eigenvectors, and we introduce 
permutations before the back transformation of each rank-one update in 
order to make good use of deflation.  This algortithm yields the first 
scalable, portable and numerically stable parallel divide and conquer 
eigensolver.  Numerical results confirm the effectiveness of our 
algorithm.  We compare performance of the algorithm with that of the QR 
algorithm and of bisection followed by inverse iteration on an IBM SP2 
and a cluster of Pentium PII's.

Key Words:  Divide and conquer, symmetric eigenvalue problem, tridiagonal 
matrix, rank-one modification, parallel algorithm, ScaLAPACK, LAPACK, 
distributed memory architecture

AMS subject classifications: 65F15, 68C25

------------------------------------------------------------------------------
Francoise Tisseur
ftisseur@ma.man.ac.uk
Department of Mathematics
University of Manchester

Jack Dongarra
dongarra@cs.utk.edu
Department of Computer Science
University of Tennessee - Knoxville