Solving linear matrices in an integrated circuit device

• US 8,539,014 B2
• Filed: 03/25/2010
• Issued: 09/17/2013
• Est. Priority Date: 03/25/2010
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin, Dhanoa, Kulwinder
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US12/731,310
• Publication Number:
  US 20110238720A1
• Time in Patent Office: 1,272 Days
• Field of Search: 708/446
• US Class Current: 708/446
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations
• 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 solving linear matrix equations involving a resultant matrix, an unknown matrix and a product matrix that is a product of the resultant matrix and the unknown matrix includes matrix decomposition circuitry for triangulating an input matrix to create a resultant matrix having a plurality of resultant matrix elements on a diagonal, and having a further plurality of resultant matrix elements arranged in columns below the resultant matrix elements on the diagonal. The matrix decomposition circuitry includes an inverse square root multiplication path that computes diagonal elements of the resultant matrix having an inverse square root module, and the said inverse square root module computes inverses of the diagonal elements to be used in multiplication in place of division by a diagonal element. Latency is hidden by operating on each nth row of a plurality of matrices prior to any (n+1)th row.

Claims

1. Circuitry for solving linear matrix equations involving a resultant matrix, an unknown matrix and a product matrix that is a product of said resultant matrix and said unknown matrix, said circuitry comprising:

matrix decomposition circuitry for triangulating an input matrix to create a resultant matrix having a plurality of resultant matrix elements on a diagonal, and having a further plurality of resultant matrix elements arranged in columns below said resultant matrix elements on said diagonal, said matrix decomposition circuitry comprising an inverse square root multiplication path that computes diagonal elements of said resultant matrix; and

first, second and third matrix memories for respectively storing said resultant matrix, said unknown matrix and said product matrix;

wherein;

said inverse square root multiplication path includes an inverse square root module, and

said inverse square root module computes inverses of said diagonal elements.

2. The circuitry of claim 1 wherein:

said first matrix memory stores each element of said resultant matrix as a real and imaginary part;

each said diagonal element has only a real part; and

respective ones of said inverses of said diagonal elements are stored in place of nonexistent imaginary parts of respective ones of said diagonal elements.

3. The circuitry of claim 1 further comprising:

multipliers and a summing circuit for forming an inner product of corresponding rows of said resultant matrix and said unknown matrix;

a subtractor for respectively subtracting said inner product from respective elements of said product matrix to yield respective differences; and

a further multiplier for multiplying each respective difference by a respective one of said inverses of said diagonal elements to determine respective elements of said unknown matrix.

4. A method of operating circuitry for solving linear matrix equations involving a resultant matrix, an unknown matrix and a product matrix that is a product of said resultant matrix and said unknown matrix, said circuitry comprising matrix decomposition circuitry for triangulating an input matrix to create a resultant matrix having a plurality of resultant matrix elements on a diagonal, and having a further plurality of resultant matrix elements arranged in columns below said resultant matrix elements on said diagonal, said matrix decomposition circuitry comprising an inverse square root multiplication path that computes diagonal elements of said resultant matrix, said circuitry further comprising first, second and third matrix memories for respectively storing said resultant matrix, said unknown matrix and said product matrix;

wherein said inverse square root multiplication path includes an inverse square root module, and said inverse square root module computes inverses of said diagonal elements wherein said inverse square root multiplication path includes an inverse square root module, and said inverse square root module computes inverses of said diagonal elements;

said method comprising;

storing a respective plurality of at least one of said resultant matrix and said product matrix in a respective one of said first and third matrix memories, each row of each matrix in said first and third matrix memories having a row index, wherein row indices repeat from one matrix in each respective plurality of matrices to another matrix in said respective plurality of matrices; and

for each row index, processing all rows in each matrix in at least one of said respective plurality of matrices having said row index prior to processing any rows of any matrix in said at least one of said respective plurality of matrices having any other row index.

5. A method of configuring a programmable integrated circuit device as circuitry for solving linear matrix equations involving a resultant matrix, an unknown matrix and a product matrix that is a product of said resultant matrix and said unknown matrix, said method comprising:

configuring logic of said programmable integrated circuit device as matrix decomposition circuitry for triangulating an input matrix to create a resultant matrix having a plurality of resultant matrix elements on a diagonal, and having a further plurality of resultant matrix elements arranged in columns below said resultant matrix elements on said diagonal, comprising configuring logic of said programmable integrated circuit device as an inverse square root multiplication path that computes diagonal elements of said resultant matrix; and

configuring memory of said programmable integrated circuit device as first, second and third matrix memories for respectively storing said resultant matrix, said unknown matrix and said product matrix;

wherein;

said inverse square root multiplication path includes an inverse square root module, and

said inverse square root module computes inverses of said diagonal elements.

6. The method of claim 5 wherein:

each said diagonal element has only a real part;

said method further comprises configuring said first matrix memory to store each element of said resultant matrix as a real and imaginary part; and

respective ones of said inverses of said diagonal elements are stored in place of nonexistent imaginary parts of respective ones of said diagonal elements.

7. The method of claim 5 further comprising:

configuring logic of said programmable integrated circuit device as multipliers and a summing circuit for forming an inner product of corresponding rows of said resultant matrix and said unknown matrix;

configuring logic of said programmable integrated circuit device as a subtractor for respectively subtracting said inner product from respective elements of said product matrix to yield respective differences; and

configuring logic of said programmable integrated circuit device as a further multiplier for multiplying each respective difference by a respective one of said inverses of said diagonal elements to determine respective elements of said unknown matrix.

8. A programmable integrated circuit device configured as circuitry for solving linear matrix equations involving a resultant matrix, an unknown matrix and a product matrix that is a product of said resultant matrix and said unknown matrix, said programmable integrated circuit device comprising:

logic configured as matrix decomposition circuitry for triangulating an input matrix to create a resultant matrix having a plurality of resultant matrix elements on a diagonal, and having a further plurality of resultant matrix elements arranged in columns below said resultant matrix elements on said diagonal, comprising logic configured as an inverse square root multiplication path that computes diagonal elements of said resultant matrix; and

logic configured as first, second and third matrix memories for respectively storing said resultant matrix, said unknown matrix and said product matrix;

wherein;

said inverse square root multiplication path includes an inverse square root module, and

said inverse square root module computes inverses of said diagonal elements.

9. The configured programmable integrated circuit device of claim 8 wherein:

each said diagonal element has only a real part;

said first matrix memory is configured to store each element of said resultant matrix as a real and imaginary part; and

respective ones of said inverses of said diagonal elements are stored in place of nonexistent imaginary parts of respective ones of said diagonal elements.

10. The configured programmable integrated circuit device of claim 8 further comprising:

logic configured as multipliers and a summing circuit for forming an inner product of corresponding rows of said resultant matrix and said unknown matrix;

logic configured as a subtractor for respectively subtracting said inner product from respective elements of said product matrix to yield respective differences; and

logic configured as a further multiplier for multiplying each respective difference by a respective one of said inverses of said diagonal elements to determine respective elements of said unknown matrix.

11. A machine-readable data storage medium encoded with machine-executable instructions for configuring a programmable integrated circuit device as circuitry for solving linear matrix equations involving a resultant matrix, an unknown matrix and a product matrix that is a product of said resultant matrix and said unknown matrix, said instructions comprising:

instructions to configure logic of said programmable integrated circuit device as matrix decomposition circuitry for triangulating an input matrix to create a resultant matrix having a plurality of resultant matrix elements on a diagonal, and having a further plurality of resultant matrix elements arranged in columns below said resultant matrix elements on said diagonal, comprising instructions to configure logic of said programmable integrated circuit device as an inverse square root multiplication path that computes diagonal elements of said resultant matrix; and

instructions to configure memory of said programmable integrated circuit device as first, second and third matrix memories for respectively storing said resultant matrix, said unknown matrix and said product matrix;

wherein;

said inverse square root multiplication path includes an inverse square root module, and

said inverse square root module computes inverses of said diagonal elements.

12. The machine-readable data storage medium of claim 11 wherein:

each said diagonal element has only a real part;

said instructions to configure said first matrix memory comprise instructions to configure said first matrix memory to store each element of said resultant matrix as a real and imaginary part; and

respective ones of said inverses of said diagonal elements are stored in place of nonexistent imaginary parts of respective ones of said diagonal elements.

13. The machine-readable data storage medium of claim 11 wherein said instructions further comprise:

instructions to configure logic of said programmable integrated circuit device as multipliers and a summing circuit for forming an inner product of corresponding rows of said resultant matrix and said unknown matrix;

instructions to configure logic of said programmable integrated circuit device as a subtractor for respectively subtracting said inner product from respective elements of said product matrix to yield respective differences; and

instructions to configure logic of said programmable integrated circuit device as a further multiplier for multiplying each respective difference by a respective one of said inverses of said diagonal elements to determine respective elements of said unknown matrix.