Patent ID: 7937425

Claim:
A method for performing singular value decomposition (SVD) of a matrix using two-plane rotation, comprising: computing two-plane rotation terms of rotation and reflection in a rotation processor based on elements of the matrix, wherein the rotation processor comprises: an array of 2 by 2 processors including diagonal processors and off-diagonal processors, each comprising a control read-only memory (ROM), and a master controller configured to control the array of 2 by 2 processors and cause the control ROMs to load or compute the SVD; determining rotation angles in the diagonal processors of the rotation processor based on the two-plane rotation terms; determining sign terms in the diagonal processors of the rotation processor based on the two-plane rotation terms; computing primary rotation terms in the diagonal processors of the rotation processor based on the rotation angles and the sign terms, wherein at least part of computation of the primary rotation terms in the rotation processor is based on a trigonometric value from a trigonometric lookup table, wherein the trigonometric lookup table does not calculate the trigonometric value, wherein the primary rotation terms comprise sin θ R , sin θ L , cos θ R , and cos θ L , where sin θ R =s 2 sin γ cos φ+s 1 cos γ sin φ, sin θ L =s 2 sin γ cos φ−s 1 cos γ sin φ, cos θ R =cos γ cos φ−s 1 s 2 sin γ sin φ, and cos θ L =cos γ cos φ+s 1 s 2 sin γ sin φ; wherein determining the rotation angles, determining the sign terms, and computing the primary rotation terms each produce results and are only performed if solving a 2 by 2 SVD or if solving a diagonal portion of an overall matrix that is larger than a 2 by 2 SVD; broadcasting the results relevant to solving any corresponding off-diagonal portions; computing local rotation terms in the rotation processor based on the primary rotation terms, wherein the local rotation terms are sin θ + , cos θ + , sin θ − , and cos θ − , where sin θ + =sin θ R cos θ L +cos θ R sin θ L , cos θ + =cos θ R cos θ L −sin θ R sin θ L , sin θ − =sin θ R cos θ L −cos θ R sin θ L , and cos θ − =cos θ R cos θ L +sin θ R sin θ L ; computing updated two-plane rotation terms in the rotation processor based on the local rotation terms and the two-plane rotation terms; and forming an updated matrix in the rotation processor based on the updated two-plane rotation terms.