A parallel implementation of the symmetric tridiagonal QR algorithm

Author

Arbenz, Peter ; Gates, Kevin ; Sprenger, Christoph

Author_Institution

Inst. fuer Wissenschaftliches Rechnen, Zurich, Switzerland

fYear

1992

fDate

19-21 Oct 1992

Firstpage

382

Lastpage

388

Abstract

The authors propose a novel and simple way to parallelize the QR algorithm for computing eigenvalues and eigenvectors of real symmetric tridiagonal matrices. This approach is suitable for all parallel computers, ranging from multiprocessor supercomputers with shared memory to massively parallel computers with local memory. The authors report on numerical experiments completed on a Cray-Y-MP, an Alliant FX-80, a Sequent Symmetry S81b, a nCUBE 2, a Thinking Machines CM200, and a cluster of Sun SPARCstations. The numerical results indicate that the proposed algorithm is suitable for parallel execution on the whole range of parallel computers. While the results obtained on the computers with vector facilities did not show very high efficiencies, those obtained with multiprocessor computers with scalar CPUs had very good speedups

Keywords

eigenvalues and eigenfunctions; mathematics computing; matrix algebra; parallel algorithms; Alliant FX-80; Cray-Y-MP; Sequent Symmetry S81b; Sun SPARCstations; Thinking Machines CM200; eigenvalues; eigenvectors; local memory; massively parallel computers; multiprocessor supercomputers; nCUBE 2; parallel execution; parallel implementation; real symmetric tridiagonal matrices; scalar CPUs; shared memory; symmetric tridiagonal QR algorithm; Clustering algorithms; Costs; Eigenvalues and eigenfunctions; Hypercubes; Parallel algorithms; Parallel processing; Stability; Sun; Supercomputers; Symmetric matrices;

fLanguage

English

Publisher

ieee

Conference_Titel

Frontiers of Massively Parallel Computation, 1992., Fourth Symposium on the

Conference_Location

McLean, VA

Print_ISBN

0-8186-2772-7

Type

conf

DOI

10.1109/FMPC.1992.234936

Filename

234936