Title :
A Parallel QR Algorithm for Symmetric Tridiagonal Matrices
Author :
Sameh, Ahmed H. ; Kuck, David J
Author_Institution :
Department of Computer Science and the Center for Advanced Computation, University of Illinois, Urbana, IL 61801.
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 :
Arithmetic; Computer errors; Concurrent computing; Eigenvalues and eigenfunctions; Error analysis; Hardware; Parallel algorithms; Parallel processing; Software design; Symmetric matrices; Error analysis; Givens reduction; parallelism; recurrence relations; triangular systems;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1977.5009293
