Apparatus and method for inverting a 4×4 matrix

Abstract

An apparatus and method for inverting a 4×4 source matrix. A source matrix is divided into four 2×2 sub-matrices. A plurality of sub-matrix products are subsequently calculated from the sub-matrices. Next, a determinant of the source matrix is calculated to form a determinant residue utilizing the previously computed sub-matrix products. Calculation of partial inverse for each sub-matrix is next performed, using the sub-matrix products and determinants of the sub-matrices. Finally, an inverse of each sub-matrix is calculated, utilizing the partial inverse sub-matrices and the determinant residue to form an inverse of the 4×4 source matrix. The article allows processors to store two floating-point elements within a Single Instruction Multiple Data (SIMD) register. Accordingly, a sub-matrix is represented using two SIMD registers, resulting in improved computational locality and efficiency. Other embodiments are described and claimed.

1. An article comprising a machine readable medium that stores data representing a predetermined function, the predetermined function comprising:
 dividing the source matrix into four 2×2 sub-matrices A, B, C and D; 
 calculating a plurality of sub-matrix products from the sub-matrices; 
 calculating a determinant of the source matrix dS to form a matrix determinant residue rd of the source matrix as rd=1/dS; 
 forming a partial, inverse sub-matrix of each sub-matrix using one or more of the matrix products and a determinant of each sub-matrix; and 
 calculating an inverse of each sub-matrix iA, iB, iC, and iD, utilizing each partial, inverse sub-matrix and determinant residue rd, such that an inverse of the source matrix iS is formed. 
 
   
   
     2. The article of  claim 1 , wherein dividing the source matrix S into the four 2×2 sub-matrices A, B, C and D is performed according to the following rule: 
       S   =     (         A       B           C       D         )         
 
     to enable storage of each sub-matrix within a pair of SIMD registers. 
   
   
     3. The article of  claim 1 , wherein calculating the plurality of sub-matrix products further comprises:
 calculating an intermediate sub-matrix product for each sub-matrix by computing the following matrix equations:
     {tilde over (D)}C =adj( D )· C   
     ÃB =adj( A )· B   
 
 wherein the adj function refers to an adjoint matrix operation and the dot symbol · refers to a matrix multiplication operation; and 
 calculating a final sub-matrix product for each of the intermediate sub-matrix products by computing the following equations:
     B{tilde over (D)}C=B·{tilde over (D)}C   
     D{tilde over (B)}A=D ·adj( ÃB ) 
     A{tilde over (C)}D=A ·adj( {tilde over (D)}C ) 
     CÃB=C·ÃB.   
 
 
   
   
     4. The article of  claim 1 , wherein calculating the matrix determinant residue further comprises:
 computing a determinant of each sub-matrix dA, dB, dC and dD; 
 calculating a trace value by computing a following equation:
     t =trace( ÃB·{tilde over (D)}C ); 
 
 wherein a dot symbol · refers to a matrix multiplication operation; and 
 calculating a determinant of the source matrix dS by computing a following equation:
     dS=dA*dD+dB*dC−t   
 
 wherein the symbol * refers to a scalar multiplication operation. 
 
   
   
     5. The article of  claim 1 , wherein forming partial-inverse sub-matrices further comprises:
 performing matrix scaling of a determinant of each sub-matrix as D*dA, C*dB, B*dC and A*dD; and 
 computing a partial inverse for each sub-matrix according to the following matrix scaling equations:
     pA=A*dD−B{tilde over (D)}C   
     pB=C*dB−D{tilde over (B)}A   
     pC=B*dC−A{tilde over (C)}D   
     pD=D*dA−CÃB,   
 
 wherein pA, pB, pC, and pD reference partial, inverse sub-matrices, and the symbol * refers to a matrix scaling by a scalar operation. 
 
   
   
     6. The article of  claim 1 , wherein calculating an inverse of each sub-matrix further comprises:
 calculating an adjoint value of each partial, inverse sub-matrix pA, pB, pC, and pD, according to the following rules:
     iA =adj( pA ), 
     iB =adj( pB ), 
     iC =adj( pC ), 
     iD =adj( pD ), 
 
 wherein the adj( ) function refers to the adjoint matrix operation; 
 calculating a final sub-matrix inverse value according to the following equations:
     iA=iA*rd   
     iB=iB*rd   
     iC=iC*rd   
     iD=iD*rd,   
 
 wherein the symbol * refers to a matrix scaling by a scalar operation; and 
 forming the inverse source matrix iS according to the following rule: 
       iS   =       (         iA       iB           iC       iD         )     .         
 
 
   
   
     7. An article comprising a machine readable medium that stores data representing a predetermined function, the predetermined function comprising:
 dividing a source matrix into four 2×2 sub-matrices, A, B, C and D; 
 calculating one or more intermediate sub-matrix products from one or more of the sub-matrices; 
 calculating a determinant of the source matrix to form a determinant residue rd utilizing the intermediate sub-matrix products; 
 scaling a determinant of each sub-matrix and the intermediate sub-matrix products using determinant residue rd to form final sub-matrix products; 
 forming a partial inverse sub-matrix pA, pB, pC and pD for each sub-matrix using the scaled sub-matrix determinants and the final sub-matrix products; and 
 calculating an inverse of each sub-matrix iA, iB, iC and iD, utilizing each partial inverse sub-matrix to form an inverse source matrix iS. 
 
   
   
     8. The article of  claim 7 , wherein calculating the matrix determinant residue further comprises:
 computing a determinant of each sub-matrix dA, dB, dC and dD; 
 calculating a trace value by computing a following equation:
     t =trace( ÃB·{tilde over (D)}C ); 
 
 wherein a dot symbol · refers to a matrix multiplication operation; 
 calculating a determinant of the source matrix dS by computing a following equation:
     dS=dA*dD+dB*dC−t   
 
 wherein the symbol * refers to a scalar multiplication operation; and 
 calculating the determinant residue rd according to the following rule:
     rd= 1 /dS.   
 
 
   
   
     9. The article of  claim 7 , wherein scaling by the determinant residue further comprises:
 multiplying each determinant by the determinant residue rd according to the following rules:
     dA=dA*rd   
     dB=dB*rd   
     dC=dC*rd   
     dD=dD*rd;   
 
 multiplying each intermediate sub-matrix product ÃB and {tilde over (D)}C by the determinant residue rd, according to the following equations:
     {tilde over (D)}C={tilde over (D)}C*rd   
     ÃB=ÃB*rd ; and 
 
 calculating a final sub-matrix product for each of the intermediate matrix products by computing the following equations:
     B{tilde over (D)}C=B·{tilde over (D)}C   
     D{tilde over (B)}A=D ·adj( ÃB ) 
     A{tilde over (C)}D=A ·adj( {tilde over (D)}C ) 
     CÃB=C·ÃB.   
 
 
   
   
     10. The article of  claim 7 , wherein calculating an inverse of each sub-matrix further comprises:
 generating an adjoint of each partial, inverse sub-matrix by computing the following equations:
     iA =adj( pA ) 
     iB =adj( pB ) 
     iC =adj( pC ) 
     iD =adj( pD ); and 
 
 forming the inverse source matrix is according to the following rule: 
       iS   =       (         iA       iB           iC       iD         )     .         
 
 
   
   
     11. A computer readable storage medium including program instructions that direct a computer to function in a specified manner when executed by a processor, the program instructions comprising:
 dividing the source matrix into four 2×2 sub-matrices A, B, C and D; 
 calculating a plurality of sub-matrix products from the sub-matrices; 
 calculating a determinant of the source matrix dS to form a matrix determinant residue rd of the source matrix as rd=1/dS; 
 forming a partial, inverse sub-matrix of each sub-matrix using one or more of the matrix products and a determinant of each sub-matrix; and 
 calculating an inverse of each sub-matrix iA, iB, iC, and iD, utilizing each partial, inverse sub-matrix and determinant residue rd, such that an inverse of the source matrix iS is formed. 
 
   
   
     12. The computer readable storage medium of  claim 11 , wherein dividing the source matrix S into the four 2×2 sub-matrices A, B, C and D is performed according to the following rule: 
       S   =     (         A       B           C       D         )         
 
     to enable storage of each sub-matrix within a pair of SIMD registers. 
   
   
     13. The computer readable storage medium of  claim 11 , wherein calculating the plurality of sub-matrix products further comprises:
 calculating an intermediate sub-matrix product for each sub-matrix by computing the following matrix equations:
     {tilde over (D)}C =adj( {tilde over (D)} )· C   
     ÃB =adj( A )· B   
 
 wherein the adj( ) function refers to an adjoint matrix operation and the dot symbol · refers to a matrix multiplication operation; and 
 calculating a final sub-matrix product for each of the intermediate sub-matrix products by computing the following equations:
     B{tilde over (D)}C=B·{tilde over (D)}C   
     D{tilde over (B)}A=D ·adj( ÃB ) 
     A{tilde over (C)}D=A ·adj( {tilde over (D)}C ) 
     CÃB=C·ÃB.   
 
 
   
   
     14. The computer readable storage medium of  claim 11 , wherein calculating the matrix determinant residue further comprises:
 computing a determinant of each sub-matrix dA, dB, dC and dD; 
 calculating a trace value by computing a following equation:
     t =trace( ÃB·{tilde over (D)}C ); 
 
 wherein a dot symbol · refers to a matrix multiplication operation; and 
 calculating a determinant of the source matrix dS by computing a following equation:
     dS=dA*dD+dB*dC−t   
 
 wherein the symbol * refers to a scalar multiplication operation. 
 
   
   
     15. The computer readable storage medium of  claim 11 , wherein forming partial-inverse sub-matrices further comprises:
 performing matrix scaling of a determinant of each sub-matrix as D*dA, C*dB, B*dC and A*dD; and 
 computing a partial inverse for each sub-matrix according to the following matrix scaling equations:
     pA=A*dD−{tilde over (B)}DC   
     pB=C*dB−{tilde over (D)}BA   
     pC=B*dC−ÃCD   
     pD=D*dA−{tilde over (C)}AB,   
 
 wherein pA, pB, pC, and pD reference partial, inverse sub-matrices, and the symbol * refers to a matrix scaling by a scalar operation. 
 
   
   
     16. The computer readable storage medium of  claim 11 , wherein calculating an inverse of each sub-matrix further comprises:
 calculating an adjoint value of each partial, inverse sub-matrix pA, pB, pC, and pD, according to the following rules:
     iA =adj( pA ), 
     iB =adj( pB ), 
     iC =adj( pC ), 
     iD =adj( pD ), 
 
 wherein the adj( ) function refers to the adjoint matrix operation; 
 calculating a final sub-matrix inverse value according to the following equations:
     iA=iA*rd   
     iB=iB*rd   
     iC=iC*rd   
     iD=iD*rd,   
 
 wherein the symbol * refers to a matrix scaling by a scalar operation; and 
 forming the inverse source matrix iS according to the following rule: 
       iS   =       (         iA       iB           iC       iD         )     .         
 
 
   
   
     17. The computer readable storage medium including program instructions that direct a computer to function in a specified manner when executed by a processor, the program instructions comprising:
 dividing a source matrix into four 2×2 sub-matrices, A, B, C and D; 
 calculating one or more intermediate sub-matrix products from one or more of the sub-matrices; 
 calculating a determinant of the source matrix dS to form a determinant residue rd of the source matrix utilizing the intermediate sub-matrix products and the sub-matrix determinants; 
 scaling a determinant of each sub-matrix and the intermediate sub-matrix products using determinant residue rd to form final sub-matrix products; 
 forming a partial inverse sub-matrix pA, pB, pC and pD for each sub-matrix using the scaled sub-matrix determinants and the final sub-matrix products; and 
 calculating an inverse of each sub-matrix iA, iB, iC and iD, utilizing each partial inverse sub-matrix to form an inverse source matrix iS. 
 
   
   
     18. The computer readable storage medium of  claim 17 , wherein calculating the matrix determinant residue further comprises:
 computing a determinant of each sub-matrix dA, dB, dC and dD; 
 calculating a trace value by computing a following equation:
     t =trace( ÃB·{tilde over (D)}C ); 
 
 wherein a dot symbol · refers to a matrix multiplication operation; 
 calculating a determinant of the source matrix dS by computing a following equation:
     dS=dA*dD+dB*dC−t   
 
 wherein the symbol * refers to a scalar multiplication operation; and 
 calculating the determinant residue rd according to the following rule:
     rd= 1 /dS.   
 
 
   
   
     19. The computer readable storage medium of  claim 17 , wherein scaling by the determinant residue further comprises:
 multiplying each determinant by the determinant residue rd according to the following rules:
     dA=dA*rd   
     dB=dB*rd   
     dC=dC*rd   
     dD=dD*rd;   
 
 multiplying each intermediate sub-matrix product by the determinant residue rd, according to the following equations:
     {tilde over (D)}C={tilde over (D)}C*rd   
     ÃB=ÃB*rd ; and 
 
 calculating a final sub-matrix product for each of the intermediate matrix products by computing the following equations:
     B{tilde over (D)}C=B·{tilde over (D)}C   
     D{tilde over (B)}A=D ·adj( ÃB ) 
     A{tilde over (C)}D=A ·adj( {tilde over (D)}C ) 
     CÃB=C·ÃB.   
 
 
   
   
     20. The computer readable storage medium of  claim 17 , wherein calculating an inverse of each sub-matrix further comprises:
 generating an adjoint of each partial, inverse sub-matrix by computing the following equations:
     iA =adj( pA ) 
     iB =adj( pB ) 
     iC =adj( pC ) 
     iD =adj( pD ); and 
 
 forming the inverse source matrix iS according to the following rule: 
       iS   =       (         iA       iB           iC       iD         )     .         
 
 
   
   
     21. An apparatus, comprising:
 a processor having circuitry to execute instructions; 
 a plurality of SIMD data storage devices coupled to the processor, the SIMD data storage registers to pairs of floating point vectors during matrix calculation; 
 a storage device coupled to the processor, having sequences of instructions stored therein, which when executed by the processor cause the processor to:
 divide the source matrix into four 2×2 sub-matrices A, B, C and D; 
 calculate a plurality of sub-matrix products from the sub-matrices; 
 calculate a determinant of the source matrix dS to form a determinant residue rd of the source matrix as rd=1/dS; 
 form a partial, inverse sub-matrix of each sub-matrix using one or more of the matrix products and the determinant of each sub-matrix; and 
 calculate an inverse of each sub-matrix iA, iB, iC, and iD, utilizing each partial, inverse sub-matrix and determinant residue rd, such that an inverse of the source matrix iS is formed. 
 
 
   
   
     22. The apparatus of  claim 21 , wherein the instruction to calculate the plurality of sub-matrix products further causes the processor to:
 calculate an intermediate sub-matrix product for each sub-matrix by computing the following matrix equations:
     {tilde over (D)}C =adj( {tilde over (D)} )· C   
     ÃB =adj( A )· B   
 
 wherein the adj( ) function refers to an adjoint matrix operation and the dot symbol · refers to a matrix multiplication operation; and 
 calculate a final sub-matrix product for each of the intermediate sub-matrix products by computing the following equations:
     B{tilde over (D)}C=B·{tilde over (D)}C   
     D{tilde over (B)}A=D ·adj( ÃB ) 
     A{tilde over (C)}D=A ·adj( {tilde over (D)}C ) 
     CÃB=C·ÃB.   
 
 
   
   
     23. The apparatus of  claim 21 , wherein the instruction to calculate the matrix determinant residue further causes the processor to:
 compute a determinant of each sub-matrix dA, dB, dC and dD; 
 calculate a trace value by computing a following equation:
     t =trace( ÃB·{tilde over (D)}C ); 
 
 wherein a dot symbol · refers to a matrix multiplication operation; and 
 calculate a determinant of the source matrix dS by computing a following equation:
     dS=dA*dD+dB*dC−t   
 
 
     wherein the symbol * refers to a scalar multiplication operation. 
   
   
     24. The apparatus of  claim 21 , wherein the instruction to perform matrix scaling further causes the processor to:
 perform matrix scaling of a determinant of each sub-matrix as D*dA, C*dB, B*dC and A*DdD; 
 compute a partial inverse for each sub-matrix according to the following matrix scaling equations:
     pA=A*dD−B{tilde over (D)}C   
     pB=C*dB−D{tilde over (B)}A   
     pC=B*dC−A{tilde over (C)}D   
     pD=D*dA−CÃB,   
 
 wherein pA, pB, pC, and pD reference partial, inverse sub-matrices and the symbol * refers to a matrix scaling by a scalar operation. 
 
   
   
     25. The apparatus of  claim 21 , wherein the instruction to calculate an inverse of each sub-matrix further causes the processor to:
 calculate an adjoint value of each partial, inverse sub-matrix pA, pB, pC, and pD, according to the following rules:
     iA =adj( pA ), 
     iB =adj( pB ), 
     iC =adj( pC ), 
     iD =adj( pD ), 
 
 wherein the adj( ) function refers to the adjoint matrix operation; 
 calculate a final sub-matrix inverse value according to the following equations:
     iA=iA*rd   
     iB=iB*rd   
     iC=iC*rd   
     iD=iD*rd,   
 
 wherein the symbol * refers to a matrix scaling by a scalar operation; and 
 form the inverse source matrix iS according to the following rule: 
       iS   =       (         iA       iB           iC       iD         )     .         
 
 
   
   
     26. A system, comprising:
 a processor having circuitry to execute instructions; 
 a plurality of SIMD data storage devices coupled to the processor, the SIMD data storage registers to pairs of floating point vectors during matrix calculation; 
 a storage device coupled to the processor, having sequences of instructions stored therein, which when executed by the processor cause the processor to:
 divide a source matrix into four 2×2 sub-matrices, A, B, C and D; 
 calculate one or more intermediate sub-matrix products from each of the sub-matrices, 
 calculate a source matrix dS to form a determinant residue rd utilizing the intermediate sub-matrix products, 
 scale a determinant of each sub-matrix and the intermediate sub-matrix products using determinant residue rd to form final sub-matrix products, 
 form a partial inverse sub-matrix pA, pB, pC and pD for each sub-matrix using the scaled sub-matrix determinants and the final sub-matrix products, and 
 calculate an inverse of each sub-matrix iA, iB, iC and iD, utilizing each partial inverse sub-matrix to form an inverse source matrix iS. 
 
 
   
   
     27. The system of  claim 26 , wherein the instruction to calculate the source matrix determinant residue further causes the processor to:
 compute a determinant of each sub-matrix dA, dB, dC and dD; 
 calculate a trace value by computing a following equation:
     t =trace( ÃB·{tilde over (D)}C ) 
 
 wherein a dot symbol · refers to a matrix multiplication operation; 
 calculate a determinant of the source matrix dS by computing a following equation:
     dS=dA*dD+dB*dC−t   
 
 wherein the symbol * refers to a scalar multiplication operation; and 
 calculate the determinant residue rd according to the following rule:
     rd= 1 /dS.   
 
 
   
   
     28. The system of  claim 26 , wherein the instruction to scale by the determinant residue further causes the processor to:
 multiply each determinant by the determinant residue rd according to the following rules:
     dA=dA*rd   
     dB=dB*rd   
     dC=dC*rd   
     dD=dD*rd;   
 
 multiply each intermediate sub-matrix product ÃB and {tilde over (D)}C by the determinant residue rd, according to the following equations:
     {tilde over (D)}C={tilde over (D)}C*rd   
     ÃB=ÃB*rd ; and 
 
 calculate a final sub-matrix product for each of the intermediate matrix products by computing the following equations:
     B{tilde over (D)}C=B·{tilde over (D)}C   
     D{tilde over (B)}A=D ·adj( ÃB ) 
     A{tilde over (C)}D=A ·adj( {tilde over (D)}C ) 
     CÃB=C·ÃB.   
 
 
   
   
     29. The system of  claim 26 , wherein the instruction to calculate an inverse of each sub-matrix further causes the processor to:
 generate an adjoint of each partial, inverse sub-matrix by computing the following equations:
     iA =adj( pA ) 
     iB =adj( pB ) 
     iC =adj( pC ) 
     iD =adj( pD ); and 
 
 form the inverse source matrix iS according to the following rule: 
       iS   =       (         iA       iB           iC       iD         )     .         
 
 
   
   
     30. A method comprising:
 dividing a source matrix into four 2×2 sub-matrices A, B, C and D; 
 storing each two element row of each 2×2 sub-matrix within a single instruction multiple data (SIMD) register; 
 forming a partial, inverse sub-matrix of each sub-matrix using one or more of a plurality of sub-matrix products calculated from the sub-matrices and a determinant of each sub-matrix within one or more SIMD registers; and 
 calculating an inverse of each sub-matrix iA, iB, iC and iD, utilizing each partial, inverse sub-matrix and a determinant residue rd calculated from the source matrix, such that an inverse of the source matrix iS is formed within the one or more SIMD registers. 
 
   
   
     31. The method of  claim 30 , wherein forming the partial inverse sub-matrix further comprises:
 calculating the plurality of sub-matrix products from the sub-matrices; and 
 calculating the determinant of the source matrix Ds to form the matrix determinant residue rd of the source matrix as rd=1/Ds. 
 
   
   
     32. The method of  claim 30 , wherein dividing the source matrix S into the four 2×2 sub-matrices A, B, C and D is performed according to the following rule: 
       S   =     (         A       B           C       D         )         
 
     to enable storage of each sub-matrix within a pair of SIMD registers. 
   
   
     33. The method of  claim 31 , wherein calculating an inverse of each sub-matrix further comprises:
 calculating an adjoint value of each partial, inverse sub-matrix pA, pB, pC, and pD, according to the following rules:
     iA =adj( pA ), 
     iB =adj( pB ), 
     iC =adj( pC ), 
     iD =adj( pD ), 
 
 wherein the adj( ) function refers to the adjoint matrix operation; 
 calculating a final sub-matrix inverse value according to the following equations:
     iA=iA*rd   
     iB=iB*rd   
     iC=iC*rd   
     iD=iD*rd,   
 
 wherein the symbol * refers to a matrix scaling by a scalar operation; and 
 form the inverse source matrix iS according to the following rule: 
       iS   =       (         iA       iB           iC       iD         )     .