A Systolic Architecture for Almost Linear-Time Solution of the Symmetric Eigenvalue Problem

Abstract

An algorithm is presented for computing the eigenvalues and eigenvectors of an n x n real symmetric matrix. The algorithm is essentially a Jacobi method implemented on a two-dimensional systolic array of $O(n^{2})$ processors with nearest-neighbor communication between processors. The speedup over the serial Jacobi method is $\Theta(n^{2})$, so the algorithm converges to working accuracy in time $O(nS))$, where $S$ is the number of sweeps (typically $S \leq 10)$. Key Words and Phrases: Eigenvalue decomposition, real symmetric matrices, Hermitian matrices, Jacobi method, linear-time computation, systolic arrays, VLSI, real-time computation.