LL Logo

THIRD ANNUAL
ASAP '95 WORKSHOP

____

SinVaD-An Architecture
for Parallel Computation of the Singular Value
Decomposition

Charles M. Rader
MIT Lincoln Laboratory
244 Wood Street
Lexington, MA 02173-9108
email: rader@ll.mit.edu

Abstract A highly parallel architecture for computing the singular value decomposition of an N x N square matrix was developed by Brent and Luk, based on the Jacobi algorithm. N/2 simultaneous Jacobi transformations are performed. Each involves both premultiplication and postmultiplication by rotation matrices. The entire matrix is partitioned into (N/2) 2 2 x 2 submatrices and each submatrix is premultiplied by a rotation matrix generated in its row and postmultiplied by a rotation matrix generated in its column, so (N/2) 2 identical operations happen at the same time. Since these operations are rotations, the use of the CORDIC technique is very natural, but determination of the CORDIC control parameters for Jacobi rotations is clumsy and unnatural, which eliminates a major advantage of the CORDIC technique. We have developed an alternative semi-CORDIC technique which has the simplicity of a CORDIC implementation but for which the determination of its control parameters and their use to control Jacobi rotations is very similar. This leads to a highly parallel realization of the algorithm as a hardware array of identical circuits, each of which is very simple. We call it the SinVaD architecture. SinVaD will be capable of decomposing a 100 x 100 real matrix or a 50 x 50 complex matrix in a few milliseconds.

____

 


LL Logo Disclaimer

Direct comments and questions to: webmaster@ll.mit.edu

MIT Lincoln Laboratory. All rights reserved.