Cholesky Factorization

next up previous
Next: Performance Results Up: Factorization Routines Previous: QR Factorization

Cholesky Factorization


Cholesky factorization factors an , symmetric, positive-definite matrix into the product of a lower triangular matrix and its transpose, i.e., (or , where is upper triangular). It is assumed that the lower triangular portion of is stored in the lower triangle of a two-dimensional array and that the computed elements of overwrite the given elements of . At the -th step, we partition the matrices , , and , and write the system as

where the block is , is , and is . and are lower triangular.

The block-partitioned form of Cholesky factorization may be inferred inductively as follows. If we assume that , the lower triangular Cholesky factor of , is known, we can rearrange the block equations,

A snapshot of the block Cholesky factorization algorithm in Figure 5 shows how the column panel ( and ) is computed and how the trailing submatrix is updated. The factorization can be done by recursively applying the steps outlined above to the matrix .

Figure 5: A snapshot of block Cholesky factorization.

In the right-looking version of the LAPACK routine, the computation of the above steps involves the following operations:

  1. DPOTF2: Compute the Cholesky factorization of the diagonal block .

  2. DTRSM: Compute the column panel ,

  3. DSYRK: Update the rest of the matrix,

The parallel implementation of the corresponding ScaLAPACK routine, PDPOTRF, proceeds as follows:

  1. PDPOTF2: The process , which has the diagonal block , performs the Cholesky factorization of .

  2. PDTRSM: is broadcast columnwise by down all rows in the current column of processes, which computes the column of blocks of .

  3. PDSYRK: the column of blocks is broadcast rowwise across all columns of processes and then transposed. Now, processes have their own portions of and . They update their local portions of the matrix .

next up previous
Next: Performance Results Up: Factorization Routines Previous: QR Factorization

Susan Ostrouchov
Fri Apr 28 09:37:26 EDT 1995