A Parallel QR Algorithm for Symmetric Tridiagonal Matrices

1 February 1977

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-26 (2), 147-153
https://doi.org/10.1109/TC.1977.5009293

Abstract

We show that if the size of the tridiagonal matrix in any given iteration is n, then the parallel QR algorithm requires 0(log2n) steps with 0(n) processors per iteration and no square roots. This results in a speedup of 0(n/log2n) over the sequential algorithm with an efficiency of 0(1/log2n). We also give an error analysis of the parallel triangular system solvers used in each iteration.

Keywords

PROGRAM PROCESSORS
ALGORITHM DESIGN AND ANALYSIS
DATA MINING
PROBABILITY DENSITY FUNCTION
SYMMETRIC MATRICES
ERROR ANALYSIS
COMPUTERS

Cited by 36 articles