TRIDIAGONALIZATION OF A SYMMETRIC MATRIX ON A SQUARE ARRAY OF MESH-CONNECTED PROCESSORS

A. BOJANCZYK AND R. P. BRENT

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

Only the Abstract is given here. The full paper appeared as [1]. It is interesting that both the direct reduction to tridiagonal form, and the iterative eigenvalue computation by Jacobi-like methods [2], seem to require time Ω(n log n). The choice of which approach to the symmetric eigenvalue problem is best may depend on details of the parallel machine architecture.

References

1. A. W. Bojańczyk 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. Also appeared as Report CMA-R45-83, CMA, ANU, December 1983, 23 pp. rpb086.

2. 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. rpb084.

Centre for Mathematical Analysis, Australian National University, Canberra

1991 Mathematics Subject Classification. Primary 65Y05; Secondary 65F15, 65Y10, 68Q35. Key words and phrases. Tridiagonalization, eigenvalues, Givens rotations, plane rotations, similarity

transformations, QR algorithm, parallel algorithms, special-purpose hardware, systolic arrays, VLSI. Received October 22, 1984. We thank H. T. Kung for suggesting the problem and for helpful discussions during November 1982. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1985, Academic Press, Inc. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb086a typeset using AMS-L^{A}TEX