Procedure for computing the Cholesky decomposition in a parallel multiprocessor system

1. A process for computing a Cholesky decomposition of a positive definite matrix into a product of a lower and an upper triagonal matrix having a dimension of L in a multi-channel procedure, the process comprising the acts of:

performing the computation in a parallel multi-processor system comprising a number P of processor modules;

each processor module p computes the entries of a set R of rows of the lower triagonal matrix with R=L/P, whereby a given row j is assigned to a processor module p such that j=p+(r−1)·P with r=1. . . , R and p=1, . . . , P;

entries of the lower triagonal matrix are obtained by an iteration process over the columns i, with i=1, . . . , L, whereby in each iteration step each processor module computes the entries of column i for its assigned rows R;

upon beginning an iteration step for computing the entries of column i with i≦L, the processor module to which the computation of row number i is assigned, stores its values of row i for access by the other processor modules; and

wherein the computation of entry a ji of column i and row j is given by

a

j

⁢

⁢

i

=



a

i

,

i

-

1



-

1

·

(

c

i

⁢

⁢

j

-

∑

k

=

1

i

-

1

⁢

⁢

a

i

⁢

⁢

k

·

a

j

⁢

⁢

k

*

)

 with c ij being the corresponding value of the original matrix to be Cholesky decomposed, ∥a i,i−1 ∥ −1 being the length of the vector consisting of the already determined i−1 values of the i th row, and a jk * denoting the complex conjugation.