Modified givens rotation for matrices with complex numbers

• US 8,473,539 B1
• Filed: 09/01/2009
• Issued: 06/25/2013
• Est. Priority Date: 09/01/2009
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Rao, Raghavendar M., Dick, Christopher H.
• Primary Examiner(s): SUN, SCOTT C
• Application Number:
  US12/552,171
• Time in Patent Office: 1,393 Days
• Field of Search: None
• US Class Current: 708/522
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

Abstract

Nulling a cell of a complex matrix is described. A complex matrix and a modified Givens rotation matrix are obtained for multiplication by a processing unit, such as a systolic array or a CPU, for example, for the nulling of the cell to provide a modified form of the complex matrix. The modified Givens rotation matrix includes complex numbers c*, c, −s, and s*, wherein the complex number s* is the complex conjugate of the complex number s, and wherein the complex number c* is the complex conjugate of the complex number c. The complex numbers c and s are associated with complex numbers of the complex matrix including the cell to be nulled. The modified form is then output by the processing unit. The modified Givens rotation matrix may be implemented as a systolic array or otherwise used for processing complex numbers or matrices.

Claims

1. A method for nulling a cell of a complex matrix, comprising:

obtaining the complex matrix as input to a processing unit;

obtaining a modified Givens rotation matrix as input to the processing unit;

multiplying the complex matrix with the modified Givens rotation matrix by the processing unit for the nulling of the cell of the complex matrix to provide a modified form thereof, the modified form comprising real numbers; and

outputting the modified form by the processing unit;

the modified Givens rotation matrix including complex numbers c*, c, −

s, and s*, wherein the complex number s* is the complex conjugate of the complex number s, and wherein the complex number c* is the complex conjugate of the complex number c; and

the complex numbers c and s being associated with complex numbers of the complex matrix including the cell to be nulled.

2. The method according to claim 1, wherein the complex numbers of the complex matrix include complex numbers a and b, wherein the complex number b is located in the cell to be nulled.

3. The method according to claim 2, wherein the complex numbers c and s are respectively obtained from equations:

c=a/(√

{square root over (aa*+bb*)})=a/(√

{square root over (|a|²+|b|²)})

s=b/(√

{square root over (aa*+bb*)})=b/(√

{square root over (|a|²+|b|²)})

wherein a divisor for each of the equations is real valued.

4. The method according to claim 1, wherein the modified Givens rotation matrix is a unitary Givens rotation matrix;

and wherein the processing unit is either a systolic array or at least one microprocessor.

5. A non-transitory machine-readable medium having stored thereon information representing instructions that, when executed by processor means, causes the processor means to perform operations for nulling a cell of a complex matrix, the operations when executed comprising:

obtaining the complex matrix;

multiplying the complex matrix with a modified Givens rotation matrix using the processor means to generate a modified form of the complex matrix, the modified form comprising real numbers; and

outputting the modified form;

the modified Givens rotation matrix including complex numbers c*, c, −

s, and s*, wherein the complex number s* is the complex conjugate of the complex number s, and wherein the complex number c* is the complex conjugate of the complex number c;

the complex numbers c*, c, −

s, and s* being calculated with the processor means; and

the complex numbers c and s being associated with complex numbers of the complex matrix including the cell to be nulled.

6. The machine-readable medium according to claim 5, wherein the operations further comprise repeating the multiplying with variations of the modified Givens rotation matrix responsive to cells to be nulled for triangularization of the complex matrix.

7. The machine-readable medium according to claim 5, wherein the complex numbers of the complex matrix include complex numbers a and b, wherein the complex number b is located in the cell to be nulled.

8. The machine-readable medium according to claim 7, wherein the complex numbers c and s are respectively calculated with the processor means from equations:

c=a/(√

{square root over (aa*+bb*)})=a/(√

{square root over (|a|²+|b|²)})

s=b/(√

{square root over (aa*+bb*)})=b/(√

{square root over (|a|²+|b|²)})

wherein a divisor for each of the equations is real valued.

9. The machine-readable medium according to claim 8, wherein the processor means includes one or more digital signal processors.

10. The machine-readable medium according to claim 9, wherein the one or more digital signal processors are all internal to a Field Programmable Gate Array.

11. The machine-readable medium according to claim 8, wherein the processor means includes one or more General-Purpose Processors.

12. An apparatus configured to perform operations for nulling a cell of a complex matrix, comprising:

a processing unit configured for;

obtaining the complex matrix;

multiplying the complex matrix with a modified Givens rotation matrix to generate a modified form of the complex matrix, the modified form comprising real numbers; and

outputting the modified form;

wherein the modified Givens rotation matrix includes complex numbers c*, c, −

s, and s*, wherein the complex number s* is the complex conjugate of the complex number s, and wherein the complex number c* is the complex conjugate of the complex number c; and

wherein the complex numbers c and s are associated with complex numbers of the complex matrix including the cell to be nulled.

13. The apparatus according to claim 12, wherein the processing unit is further configured for repeating the act of multiplying with variations of the modified Givens rotation matrix responsive to cells to be nulled for triangularization of the complex matrix.

14. The apparatus according to claim 12, wherein the complex numbers of the complex matrix include complex numbers a and b, wherein the complex number b is located in the cell to be nulled.

15. The apparatus according to claim 14, wherein the processing unit is configured to calculate the complex numbers c and s are respectively from equations:

c=a/(√

{square root over (aa*+bb*)})=a/(√

{square root over (|a|²+|b|²)})

s=b/(√

{square root over (aa*+bb*)})=b/(√

{square root over (|a|²+|b|²)})

wherein a divisor for each of the equations is real valued.

16. The apparatus according to claim 15, wherein the processing unit includes one or more digital signal processors.

17. The apparatus according to claim 16, wherein the one or more digital signal processors are internal to a Field Programmable Gate Array.

18. The apparatus according to claim 15, wherein the processing unit includes one or more General-Purpose Processors.