Patent ID: 8443031

Claim:
A systolic array for Cholesky decomposition of an N×N matrix, comprising: a plurality of processing cells, including a corner cell, N−1 boundary cells, and (N 2 −3N+2)/2 internal cells; wherein the processing cells are arranged into N−1 rows and N columns of processing cells, row 1 beginning with the corner cell at column 1 and continuing with a boundary cell followed by N−2 internal cells, and each row M, M≠1, beginning with a boundary cell at column M+1 and continuing with N-M−1 internal cells, wherein 2≦M≦N; wherein each processing cell located in row M and column L (PC M,L ) is configured to receive and process N sets of values, each set j of the N sets including a value X j received on an input X for L>=1 and a value Y j received on an input Y for L>1; wherein each internal PC M,L is configured to: compute a value A=X j −Y 1 *Y j and output the value A to the input Y of the PC M+1,L for M<N and sets j>1; and select a value B=Y j and output the value B to the input X of the PC M,L+1 , for L<=N and sets j>=1; wherein each boundary PC M,L is configured to: compute a value C=(X j −Y 1 *Y j )/((X 1 −Y 1 2 ) 1/2 ) and output the value C to the input Y of the PC M+1,L+1 for L<N and sets j>1; select a value D=Y j and output the value D to the input Y of the PC M,L+1 , for L<N and sets j>=1; compute a value Rb1=(X 1 −Y 1 2 )/(X 1 −Y 1 2 ) 1/2 ) and output the value Rb1; and select a value Rb2=Y 1 and output the value Rb2; and wherein the corner PC 1,1 is configured to: compute a value D=X j /(X 1 1/2 ) and output the value D to the input Y of the PC 1,2 for sets j>1; and compute a value Rc=X 1 /(X 1 1/2 ) and output the value Rc.