Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. A Systolic Architecture for Almost Linear-Time Solution of the Symmetric Eigenvalue Problem

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

File(s)
82-525.pdf (1.15 MB)
82-525.ps (399.6 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6364
Collections
Computer Science Technical Reports
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
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR82-525
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance