A Systolic Architecture for Almost Linear-Time Solution of the Symmetric Eigenvalue Problem
Collections
Author
Brent, Richard P.
Luk, Franklin T.
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.
Date Issued
1982-08
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR82-525
Type
technical report