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.
Abstract
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.
Comments
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