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).


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).


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