QR decomposition in an integrated circuit device

• US 8,812,576 B1
• Filed: 09/12/2011
• Issued: 08/19/2014
• Est. Priority Date: 09/12/2011
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Mauer, Volker
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US13/229,820
• Time in Patent Office: 1,072 Days
• Field of Search: 708/514, 708/520, 708/607
• US Class Current: 708/520
• 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

Circuitry for performing QR decomposition of an input matrix includes multiplication/addition circuitry for performing multiplication and addition/subtraction operations on a plurality of inputs, division/square-root circuitry for performing division and square-root operations on an output of the multiplication/addition circuitry, a first memory for storing the input matrix, a second memory for storing a selected vector of the input matrix, and a selector for inputting to the multiplication/addition circuitry any one or more of a vector of the input matrix, the selected vector, and an output of the division/square-root circuitry. On respective successive passes, a respective vector of the input matrix is read from a first memory into a second memory, and elements of a respective vector of an R matrix of the QR decomposition are computed and the respective vector of the input matrix in the first memory is replaced with the respective vector of the R matrix.

Claims

1. Matrix processing circuitry for performing QR decomposition of an input matrix, said matrix processing circuitry comprising:

multiplication/addition circuitry for performing multiplication and addition/subtraction operations on a plurality of inputs;

division/square-root circuitry for performing division and square-root operations on an output of said multiplication/addition circuitry;

a first memory for storing said input matrix;

a second memory for storing a selected vector of said input matrix; and

a selector for inputting to said multiplication/addition circuitry any one or more of a vector of said input matrix, said selected vector, and an output of said division/square-root circuitry;

wherein;

on respective successive passes;

a respective vector of said input matrix is read from said first memory into said second memory, and

said matrix processing circuitry computes elements of a respective vector of an R matrix of said QR decomposition and replaces said respective vector of said input matrix in said first memory with said respective vector of said R matrix; and

after all vectors of said input matrix have been processed, said first memory contains an output matrix of said QR decomposition.

2. The matrix processing circuitry of claim 1 further comprising control circuitry controlling which one or more of said vector of said input matrix, said selected vector, and said output of said division/square-root circuitry, are input to said multiplication/addition circuitry.

3. The matrix processing circuitry of claim 1 further comprising a feedback memory for storing said output of said division/square-root circuitry for input to said selector.

4. The matrix processing circuitry of claim 3 wherein said feedback memory is a FIFO memory.

5. The matrix processing circuitry of claim 1 wherein said output matrix contained in said first memory is said R matrix.

6. The matrix processing circuitry of claim 1 further comprising:

an output memory;

wherein;

said R matrix is stored in said output memory; and

said output matrix contained in said first memory is a Q matrix of said QR decomposition.

7. A method of performing QR decomposition of an input matrix using an integrated circuit device, said method comprising:

on respective successive passes;

reading a respective vector of said input matrix from a first memory into a second memory; and

computing elements of a respective vector of an R matrix of said QR decomposition and replacing said respective vector of said input matrix in said first memory with said respective vector of said R matrix;

wherein;

after all vectors of said input matrix have been processed, said first memory contains an output matrix of said QR decomposition.

8. The method of claim 7 wherein said output matrix contained in said first memory is said R matrix.

9. The method of claim 7 further comprising:

outputting said R matrix to an output memory;

wherein;

said output matrix contained in said first memory is a Q matrix of said QR decomposition.

10. A method of configuring a programmable integrated circuit device as circuitry for performing QR decomposition of an input matrix, said method comprising:

configuring logic of said programmable integrated circuit device as multiplication/addition circuitry for performing multiplication and addition/subtraction operations on a plurality of inputs;

configuring logic of said programmable integrated circuit device as division/square-root circuitry for performing division and square-root operations on an output of said multiplication/addition circuitry;

configuring memory on said programmable integrated circuit device as a first memory for storing said input matrix;

configuring memory on said programmable integrated circuit device as a second memory for storing a selected vector of said input matrix;

configuring logic of said programmable integrated circuit device as a selector for inputting to said multiplication/addition circuitry any one or more of a vector of said input matrix, said selected vector, and an output of said division/square-root circuitry; and

configuring said circuitry for performing QR decomposition of an input matrix to, on respective successive passes;

read a respective vector of said input matrix from said first memory into said second memory, and

compute elements of a respective vector of an R matrix of said QR decomposition and replace said respective vector of said input matrix in said first memory with said respective vector of said R matrix;

wherein;

after all vectors of said input matrix have been processed, said first memory contains an output matrix of said QR decomposition.

11. The method of claim 10 further comprising:

configuring logic of said programmable integrated circuit device as control circuitry controlling which one or more of said vector of said input matrix, said selected vector, and said output of said division/square-root circuitry, are input to said multiplication/addition circuitry.

12. The method of claim 10 further comprising:

configuring memory of said programmable integrated circuit device as a feedback memory for storing said output of said division/square-root circuitry for input to said selector.

13. The method of claim 12 comprising configuring said feedback memory as a FIFO memory.

14. The method of claim 10 wherein said output matrix contained in said first memory is said R matrix.

15. The method of claim 10 wherein:

said R matrix is stored in an output memory; and

said output matrix contained in said first memory is a Q matrix of said QR decomposition.

16. A non-transitory machine-readable data storage medium encoded with non-transitory machine-executable instructions for configuring a programmable integrated circuit device as circuitry for performing QR decomposition of an input matrix, said instructions comprising:

instructions to configure logic of said programmable integrated circuit device as multiplication/addition circuitry for performing multiplication and addition/subtraction operations on a plurality of inputs;

instructions to configure logic of said programmable integrated circuit device as division/square-root circuitry for performing division and square-root operations on an output of said multiplication/addition circuitry;

instructions to configure memory of said programmable integrated circuit device as a first memory for storing said input matrix;

instructions to configure memory of said programmable integrated circuit device as a second memory for storing a selected vector of said input matrix;

instructions to configure logic of said programmable integrated circuit device as a selector for inputting to said multiplication/addition circuitry any one or more of a vector of said input matrix, said selected vector, and an output of said division/square-root circuitry; and

instructions to configure logic of said programmable integrated circuit device to, on respective successive passes;

read a respective vector of said input matrix from said first memory into said second memory, and

compute elements of a respective vector of an R matrix of said QR decomposition and replace said respective vector of said input matrix in said first memory with said respective vector of said R matrix;

wherein;

after all vectors of said input matrix have been processed, said first memory contains an output matrix of said QR decomposition.

17. The non-transitory machine-readable data storage medium of claim 16 further comprising:

instructions to configure logic of said programmable integrated circuit device as control circuitry controlling which one or more of said vector of said input matrix, said selected vector, and said output of said division/square-root circuitry, are input to said multiplication/addition circuitry.

18. The non-transitory machine-readable data storage medium of claim 16 further comprising instructions to configure memory of said programmable integrated circuit device as a feedback memory for storing said output of said division/square-root circuitry for input to said selector.

19. The non-transitory machine-readable data storage medium of claim 16 further comprising instructions to store said R matrix as said output matrix contained in said first memory.

20. The non-transitory machine-readable data storage medium of claim 16 further comprising:

instructions to configure memory of said programmable logic device as an output memory for storing said R matrix; and

instructions to store a Q matrix of said QR decomposition said output matrix contained in said first memory.