VLSI Architecture for EVD
Mithila Nagendra · 2016
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.