Efficient VLSI architectures for matrix factorizations

Abstract

The SVD (Singular Value Decomposition) is a critical matrix factorization in many real-time computations from an application domain which includes signal processing and robotics; and complex data matrices are encountered in engineering practice. This thesis advocates the use of CORDIC (Coordinate Rotation Digital Computer) arithmetic for parallel computation of the SVD/eigenvalue decomposition of arbitrary complex/Hermitian matrices using Jacobi-like algorithms on processor arrays.\nThe algorithms and architectures derive from extending the theory of Jacobi-like matrix factorizations to multi-step and inexact pivot (2 x 2) sub-matrix diagonalizations. Based on the former approach of multi-step diagonalization, and using a two-sided 2 x 2 unitary transformation amenable to CORDIC termed ${\\cal Q}$ transformation, it is shown that an arbitrary complex 2 x 2 matrix may be diagonalized in at most two ${\\cal Q}$ transformations while one ${\\cal Q}$ transformation is sufficient to diagonalize a 2 x 2 Hermitian matrix. Inexact diagonalizations from the use of approximations to the desired transformations have been advocated in the context of Jacobi-like algorithms for reasons of efficiency. Through a unifying parameterization of approximations, efficacy of diagonalizations and expected convergence behavior, more efficient schemes than those reported in the literature are proposed for 2 x 2 real, real symmetric and Hermitian matrices. Convergence behavior of the different methods was obtained by implementing the algorithms on the CM5 using C$\\sp\\*$ and CMSSL.\nAll proposed algorithms are cast in ${\\cal Q}$ transformations and CORDIC-based VLSI processor architectures for implementation of the methods are detailed in (non-redundant) CORDIC and the redundant and on-line enhancements to CORDIC. The overhead for the evaluation of the unitary transformations in all cases is minimal, thus enabling the efficient evaluation and/or application, and pipelined execution of the two-sided 2 x 2 unitary transformations on the different systolic arrays proposed in the literature for SVD and eigenvalue decompositions.