Tridiagonalization of a symmetric matrix
using mesh-connected processors
86. A. W. Bojanczyk and R. P. Brent,
Tridiagonalization of a symmetric matrix
on a square array of mesh-connected processors,
J. Parallel and Distributed Computing 2 (1985), 261-276.
Abstract:
dvi (3K),
pdf (76K),
ps (26K).
Paper: pdf (1215K).
Abstract
A parallel algorithm for transforming an
n × n
symmetric matrix to tridiagonal form is described. The algorithm
implements Givens rotations on a square array of
n × n
processors in such a way that the transformation can be performed in
time O(n log n). The processors require only
nearest-neighbor communication. The reduction to tridiagonal form could
be the first step in the parallel solution of the symmetric eigenvalue
problem in time O(n log n).
Comments
An alternative to direct reduction is the Jacobi method, which also
seems to take time O(n log n) using of order
n2 processors: see
[79,
84].
Go to next publication
Return to Richard Brent's index page