Efficient computation for eigenvalue decomposition and singular value decomposition of matrices

Abstract

For eigenvalue decomposition, a first set of at least one variable is derived based on a first matrix being decomposed and using Coordinate Rotational Digital Computer (CORDIC) computation. A second set of at least one variable is derived based on the first matrix and using a look-up table. A second matrix of eigenvectors of the first matrix is then derived based on the first and second variable sets. To derive the first variable set, CORDIC computation is performed on an element of the first matrix to determine the magnitude and phase of this element, and CORDIC computation is performed on the phase to determine the sine and cosine of this element. To derive the second variable set, intermediate quantities are derived based on the first matrix and used to access the look-up table.

1 . A computer-program storage apparatus for decomposing a matrix comprising a memory unit having software codes stored thereon, the software codes being executable by one or more processors and the software codes comprising:
 code for deriving a first set of at least one variable based on a first matrix to be decomposed and using Coordinate Rotational Digital Computer (CORDIC) computation;   code for deriving a second set of at least one variable based on the first matrix and using a look-up table; and   code for deriving a second matrix of eigenvectors based on the first and second sets of at least one variable.   
   
   
       2 . The computer-program storage apparatus of  claim 1 , wherein the code for deriving the first set of at least one variable comprises:
 code for performing CORDIC computation on an element of the first matrix to determine magnitude and phase of the element; and   code for performing CORDIC computation on the phase of the element to determine sine and cosine of the element, and   wherein the first set of at least one variable comprises the sine and cosine of the element.   
   
   
       3 . The computer-program storage apparatus of  claim 1 , wherein the code for deriving the second set of at least one variable comprises:
 code for deriving intermediate quantities based on the first matrix; and   code for deriving the second set of at least one variable based on the intermediate quantities and using the look-up table.   
   
   
       4 . The computer-program storage apparatus of  claim 3 , wherein the code for deriving the intermediate quantities comprises:
 code for deriving a divisor for an intermediate variable based on a first element of the first matrix;   code for converting the divisor into a first binary floating-point number;   code for deriving a dividend for the intermediate variable based on second and third elements of the first matrix;   code for converting the dividend into a second binary floating-point number; and   code for forming the intermediate quantities based on the first and second floating-point numbers.   
   
   
       5 . A computer-program storage apparatus for decomposing a matrix comprising a memory unit having software codes stored thereon, the software codes being executable by one or more processors and the software codes comprising:
 code for deriving intermediate quantities based on a first matrix to be decomposed;   code for deriving at least one variable based on the intermediate quantities and using a look-up table; and   code for deriving a second matrix of eigenvectors based on the at least one variable.   
   
   
       6 . The computer-program storage apparatus of  claim 5 , wherein the code for deriving the intermediate quantities based on the first matrix comprises:
 code for deriving a divisor for an intermediate variable based on a first element of the first matrix;   code for converting the divisor into a first binary floating-point number;   code for deriving a dividend for the intermediate variable based on second and third elements of the first matrix;   code for converting the dividend into a second binary floating-point number; and   code for forming the intermediate quantities based on the first and second floating-point numbers.   
   
   
       7 . The computer-program storage apparatus of  claim 6 , wherein the code for forming the intermediate quantities based on the first and second floating-point numbers comprises:
 code for deriving a first intermediate quantity based on a mantissa of the first floating-point number;   code for deriving a second intermediate quantity based on a mantissa of the second floating-point number; and   code for deriving a third intermediate quantity based on exponents of the first and second floating-point numbers.   
   
   
       8 . The computer-program storage apparatus of  claim 7 , wherein the code for deriving the at least one variable comprises:
 code for forming an input address for the look-up table based on the first, second, and third intermediate quantities; and   code for accessing the look-up table with the input address.   
   
   
       9 . A computer-program storage apparatus for decomposing a matrix comprising a memory unit having software codes stored thereon, the software codes being executable by one or more processors and the software codes comprising:
 code for performing Coordinate Rotational Digital Computer (CORDIC) computation on an element of a first matrix to determine magnitude and phase of the element;   code for performing CORDIC computation on the phase of the element to determine sine and cosine of the element; and   code for deriving a second matrix of eigenvectors based on the magnitude, sine, and cosine of the element.   
   
   
       10 . The computer-program storage apparatus of  claim 9 , wherein the CORDIC computation on the element to determine the magnitude and phase of the element and the CORDIC computation on the phase of the element to determine sine and cosine of the element are performed in parallel. 
   
   
       11 . The computer-program storage apparatus of  claim 9 , wherein the CORDIC computation on the element to determine the magnitude and phase of the element and the CORDIC computation on the phase of the element to determine sine and cosine of the element are performed for a predetermined number of iterations. 
   
   
       12 . A computer-program storage apparatus for decomposing a matrix comprising a memory unit having software codes stored thereon, the software codes being executable by one or more processors and the software codes comprising:
 code for performing a plurality of iterations of Jacobi rotation on a first matrix of complex values with a plurality of Jacobi rotation matrices, each Jacobi rotation matrix being derived by performing eigenvalue decomposition of a correlation submatrix using Coordinate Rotational Digital Computer (CORDIC) computation, a look-up table, or both the CORDIC computation and the look-up table; and   code for deriving a first unitary matrix with orthogonal vectors based on the plurality of Jacobi rotation matrices.   
   
   
       13 . The computer-program storage apparatus of  claim 12 , wherein the code for performing the plurality of iterations of the Jacobi rotation comprises, for each iteration:
 code for forming the submatrix based on the first matrix;   code for decomposing the submatrix using the CORDIC computation, the look-up table, or both the CORDIC computation and the look-up table to obtain eigenvectors of the submatrix;   code for forming a Jacobi rotation matrix with the eigenvectors; and   code for updating the first matrix with the Jacobi rotation matrix.   
   
   
       14 . The computer-program storage apparatus of  claim 13 , wherein the code for decomposing the submatrix comprises:
 code for deriving a first set of at least one variable based on the submatrix and using the CORDIC computation;   code for deriving a second set of at least one variable based on the submatrix and using the look-up table; and   code for deriving the eigenvectors of the submatrix based on the first and second sets of at least one variable.   
   
   
       15 . The computer-program storage apparatus of  claim 12 , further comprising:
 code for deriving a diagonal matrix of eigenvalues based on the plurality of Jacobi rotation matrices.   
   
   
       16 . The computer-program storage apparatus of  claim 12 , further comprising:
 code for deriving a second matrix of complex values based on the plurality of Jacobi rotation matrices; and   code for deriving a second unitary matrix with orthogonal vectors based on the second matrix.   
   
   
       17 . The computer-program storage apparatus of  claim 16 , further comprising:
 code for deriving a diagonal matrix of singular values based on the second matrix.   
   
   
       18 . The computer-program storage apparatus of  claim 12 , further comprising:
 code for deriving a second unitary matrix with orthogonal vectors based on the plurality of Jacobi rotation matrices.   
   
   
       19 . The computer-program storage apparatus of  claim 18 , further comprising:
 code for deriving a diagonal matrix of singular values based on the plurality of Jacobi rotation matrices.   
   
   
       20 . A computer-program storage apparatus for decomposing a matrix comprising a memory unit having software codes stored thereon, the software codes being executable by one or more processors and the software codes comprising:
 code for obtaining a plurality of matrices of complex values for a plurality of transmission spans;   code for performing a plurality of iterations of Jacobi rotation on a first matrix of complex values for a first transmission span to obtain a first unitary matrix with orthogonal vectors, wherein each iteration of the Jacobi rotation utilizes eigenvalue decomposition of a correlation submatrix using Coordinate Rotational Digital Computer (CORDIC) computation, a look-up table, or both the CORDIC computation and the look-up table; and   code for performing a plurality of iterations of the Jacobi rotation on a second matrix of complex values for a second transmission span to obtain a second unitary matrix with orthogonal vectors, wherein the first unitary matrix is used as an initial solution for the second unitary matrix, wherein the first and second matrices are among the plurality of matrices, and wherein the first and second transmission spans are among the plurality of transmission spans.   
   
   
       21 . The computer-program storage apparatus of  claim 20 , further comprising:
 for each remaining one of the plurality of matrices of complex values, code for performing a plurality of iterations of the Jacobi rotation on the matrix of complex values to obtain a unitary matrix with orthogonal vectors, wherein another unitary matrix obtained for another one of the plurality of matrices is used as an initial solution for the unitary matrix.   
   
   
       22 . The computer-program storage apparatus of  claim 20 , further comprising:
 code for selecting the plurality of matrices in sequential order for decomposition.   
   
   
       23 . The computer-program storage apparatus of  claim 20 , wherein the plurality of transmission spans correspond to a plurality of frequency subbands in a multi-carrier communication system. 
   
   
       24 . The computer-program storage apparatus of  claim 20 , wherein the plurality of transmission spans correspond to a plurality of time intervals. 
   
   
       25 . The computer-program storage apparatus of  claim 20 , wherein the plurality of matrices of complex values are a plurality of channel response matrices for a plurality of frequency subbands.