The solution of singular-value and symmetric
eigenvalue problems on multiprocessor arrays
84. R. P. Brent and
F. T. Luk,
The solution of singular-value and symmetric
eigenvalue problems on multiprocessor arrays,
SIAM J. Scientific and Statistical Computing 6 (1985), 69-84.
MR 86i:65089.
A preliminary version appeared in
Proceedings of a Workshop on Mathematical Programming
and Numerical Analysis
(edited by S. Gustavson and R.S. Womersley),
CMA, ANU, 1984, 38-64.
MR 86k:65129.
Abstract:
dvi (4K),
pdf (35K),
ps (31K).
Paper: pdf (1504K).
Abstract
Parallel Jacobi-like algorithms are presented for computing a
singular-value decomposition of an
m × n matrix
(m > n) and an eigenvalue decomposition of an
n × n symmetric matrix.
A linear array of O(n)
processors is proposed for the singular-value problem; the associated
algorithm requires time O(mnS), where S is
the number of sweeps (typically S < 10).
It is conjectured that S = O(log n).
A square array of O(n2) processors with
nearest-neighbor communication is proposed for the eigenvalue problem;
the associated algorithm requires time O(nS).
Comments
This paper incorporates revisions of the two Reports
[75,
76].
For related work, see
[79,
80,
83,
86,
87,
107,
137].
Go to next publication
Return to Richard Brent's index page