## 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
*n*^{2} processors: see
[79,
84].
Go to next publication

Return to Richard Brent's index page