A systolic architecture for the symmetric eigenvalue problem

76. R. P. Brent and F. T. Luk, A systolic architecture for almost linear-time solution of the symmetric eigenvalue problem, Report TR-CS-82-10, DCS, ANU; Report TR 82-525, DCS, Cornell University; Report CMA-R03-82, CMA, ANU, August 1982, 23 pp.


An algorithm is presented for computing the eigenvalues and eigenvectors of an n × n real symmetric matrix. The algorithm is essentially a Jacobi method implemented on a two-dimensional systolic array of O(n2) processors with nearest-neighbour communication between processors. The speedup over the serial Jacobi method is of order n2, so the algorithm converges to working accuracy in time O(nS), where S is the number of sweeps.


A revision of this Report is incorporated in [84], where it is conjectured that S(n) = O(log n).

Go to next publication

Return to Richard Brent's index page