VLSI Architecture for EVD

M, Nagendra (2016) VLSI Architecture for EVD. Masters thesis, Indian Institute of Technology Hyderabad.

Text
EE14MTECH11018.pdf - Submitted Version
Restricted to Registered users only until 2 August 2019.
Download (1MB) | Request a copy

Abstract

This thesis presents a systolic algorithm for the EVD of arbitrary matrices, based on the cyclic Jacobi method with parallel ordering. Jacobi methods for singular value decomposition and the symmetric eigen value problem are of interest because they are readily parallelizable and are more accurate than QR-based methods for solving the same problem. The fast computation of eigen value decomposition is of great interest in many applications. This concerns efficient algorithms, on one hand, and their effective hardware implementation either on a multiprocessor system or as dedicated VLSI hardware, on the other hand. As a basic step in the algorithm, a two-step, two-sided unitary transformation scheme is employed to diagonalize a 2 ×2 matrix. The transformations are tailored to the use of CORDIC (Coordinate Rotation Digital Computer) algorithms for high speed arithmetic. The EVD array is modeled on the Brent-Luk-VanLoan array for SVD. An array with O(n2) processors is required to compute the EVD of a n × n matrix in O(n logn) time. A CORDIC processor calculates the angles of rotation by a fixed length sequence of shift and add operations. The length depends on the required precision and the chosen set of sequences. Approximate rotation schemes are especially appropriate for CORDIC processors. Number of sweeps increases clearly, but with a simple approximation the cost per sweep is smaller than for the exact algorithm.

[error in script]

IITH Creators: