Matrix decomposition in an integrated circuit device

• US 8,396,914 B1
• Filed: 09/11/2009
• Issued: 03/12/2013
• Est. Priority Date: 09/11/2009
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): SUN, SCOTT C
• Application Number:
  US12/557,846
• Time in Patent Office: 1,278 Days
• Field of Search: None
• 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 speeds up the Cholesky decomposition of a matrix. The circuitry can be provided in a fixed logic device, or can be configured into a programmable integrated circuit device such as a programmable logic device. The circuitry implements the following equation:

$l_{\mathrm{ij}}=\frac{a_{\mathrm{ij}}-\langle L_i,L_j\rangle }{\sqrt{a_{\mathrm{jj}}-\langle L_j,L_j\rangle }}$
When any l_ij term is calculated this way, the latency in calculating the l_jj term in the denominator has little or no effect on the l_ij term calculation. And if the calculations are properly pipelined, once the pipeline is filled, a new term can be output on each clock cycle or every few clock cycles.

Claims

1. 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, and having no nonzero matrix elements in said columns above said resultant matrix elements on said diagonal, said matrix decomposition circuitry comprising:

an inner product computation path including a plurality of multipliers and adders for computing respective inner products of row vectors of said resultant matrix corresponding to respective elements of said input matrix, and a subtractor for subtracting each said respective inner product from said respective element of said input matrix to output respective inner product difference elements corresponding to said respective elements of said input matrix;

an inverse square root multiplication path including a first storage element for latching a particular one of said respective inner product difference elements, inverse square root circuitry that computes an inverse square root of said particular one of said respective inner product difference elements, and a multiplier that multiplies said inverse square root by an output of said inner product computation path; and

a pipeline stage between said inner product computation path and said inverse square root multiplication path;

whereby;

each of said respective inner product difference elements is multiplied by said inverse square root of said particular one of said respective inner product difference elements to output a respective one of resultant matrix elements.

2. The matrix decomposition circuitry of claim 1 wherein:

said inner product computation path further comprises a second storage element for latching a particular one of said row vectors;

whereby;

said respective inner products are calculated from said particular one of said row vectors and each respective one of said row vectors.

3. The matrix decomposition circuitry of claim 2 wherein said particular one of said respective inner product difference elements and said particular one of said row vectors correspond to one of said resultant matrix elements on said diagonal.

4. A method of configuring a 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, and having no nonzero matrix elements in said columns above said resultant matrix elements on said diagonal, said method comprising:

configuring logic of said programmable integrated circuit device as an inner product computation path including a plurality of multipliers and adders for computing respective inner products of row vectors of said resultant matrix corresponding to respective elements of said input matrix, and a subtractor for subtracting each said respective inner product from said respective element of said input matrix to output respective inner product difference elements corresponding to said respective elements of said input matrix;

configuring logic of said programmable integrated circuit device as an inverse square root multiplication path including a first storage element for latching a particular one of said respective inner product difference elements, inverse square root circuitry that computes an inverse square root of said particular one of said respective inner product difference elements, and a multiplier that multiplies said inverse square root by an output of said inner product computation path; and

configuring logic of said programmable integrated circuit device as a pipeline stage between said inner product computation path and said inverse square root multiplication path;

whereby;

said configured logic multiplies each of said respective inner product difference elements by said inverse square root of said particular one of said respective inner product difference elements to output a respective one of resultant matrix elements.

5. The method of claim 4 further comprising configuring logic of said programmable integrated circuit device as a second storage element in said inner product computation path, for latching a particular one of said row vectors;

whereby;

said configured logic calculates said respective inner products from said particular one of said row vectors and each respective one of said row vectors.

6. The method of claim 5 wherein said particular one of said respective inner product difference elements and said particular one of said row vectors correspond to one of said resultant matrix elements on said diagonal.

7. A programmable integrated circuit device comprising:

logic configurable as an inner product computation path including a plurality of multipliers and adders for computing respective inner products of row vectors of said resultant matrix corresponding to respective elements of said input matrix, and a subtractor for subtracting each said respective inner product from said respective element of said input matrix to output respective inner product difference elements corresponding to said respective elements of said input matrix;

logic configurable as an inverse square root multiplication path including a first storage element for latching a particular one of said respective inner product difference elements, inverse square root circuitry that computes an inverse square root of said particular one of said respective inner product difference elements, and a multiplier that multiplies said inverse square root by an output of said inner product computation path; and

logic configurable as a pipeline stage between said inner product computation path and said inverse square root multiplication path;

whereby;

said logic is configurable to multiply each of said respective inner product difference elements by said inverse square root of said particular one of said respective inner product difference elements to output a respective one of resultant matrix elements.

8. The programmable integrated circuit device of claim 7 further comprising logic configurable as a second storage element in said inner product computation path, for latching a particular one of said row vectors;

whereby;

said logic is configurable to calculate said respective inner products from said particular one of said row vectors and each respective one of said row vectors.

9. The programmable integrated circuit device of claim 8 wherein said particular one of said respective inner product difference elements and said particular one of said row vectors correspond to one of said resultant matrix elements on said diagonal.

10. A machine-readable data storage medium encoded with machine-executable instructions for configuring a 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, and having no nonzero matrix elements in said columns above said resultant matrix elements on said diagonal, said instructions comprising:

instructions to configure logic of said programmable integrated circuit device as an inner product computation path including a plurality of multipliers and adders for computing respective inner products of row vectors of said resultant matrix corresponding to respective elements of said input matrix, and a subtractor for subtracting each said respective inner product from said respective element of said input matrix to output respective inner product difference elements corresponding to said respective elements of said input matrix;

instructions to configure logic of said programmable integrated circuit device as an inverse square root multiplication path including a first storage element for latching a particular one of said respective inner product difference elements, inverse square root circuitry that computes an inverse square root of said particular one of said respective inner product difference elements, and a multiplier that multiplies said inverse square root by an output of said inner product computation path; and

instructions to configure logic of said programmable integrated circuit device as a pipeline stage between said inner product computation path and said inverse square root multiplication path;

whereby;

said instructions cause logic to be configured to multiply each of said respective inner product difference elements by said inverse square root of said particular one of said respective inner product difference elements to output a respective one of resultant matrix elements.

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

instructions to configure logic of said programmable integrated circuit device as a second storage element in said inner product computation path, for latching a particular one of said row vectors;

whereby;

said instructions cause logic to be configured to calculate said respective inner products from said particular one of said row vectors and each respective one of said row vectors.

12. The machine-readable data storage medium of claim 11 wherein said particular one of said respective inner product difference elements and said particular one of said row vectors correspond to one of said resultant matrix elements on said diagonal.