Simple cases: <IMG ALIGN=BOTTOM SRC="_22900_tex2html_wrap6165.gif"> and <IMG ALIGN=BOTTOM SRC="_22900_tex2html_wrap6389.gif">-<IMG ALIGN=BOTTOM SRC="_22900_tex2html_wrap7381.gif">



next up previous contents index
Next: Special cases: central Up: Point incomplete factorizations Previous: Fill-in strategies

Simple cases: and -

 

For the method, the incomplete factorization produces no nonzero elements beyond the sparsity structure of the original matrix, so that the preconditioner at worst takes exactly as much space to store as the original matrix. In a simplified version of , called - (Pommerell [174]), even less is needed. If not only we prohibit fill-in elements, but we also alter only the diagonal elements (that is, any alterations of off-diagonal elements are ignoredgif), we have the following situation.

Splitting the coefficient matrix into its diagonal, lower triangular, and upper triangular parts as , the preconditioner can be written as where is the diagonal matrix containing the pivots generated. Generating this preconditioner is described in figure gif.

  
Figure: Construction of a - incomplete factorization preconditioner, storing the inverses of the pivots

Since we use the upper and lower triangle of the matrix unchanged, only storage space for is needed. In fact, in order to avoid division operations during the preconditioner solve stage we store rather than .

Remark: the resulting lower and upper factors of the preconditioner have only nonzero elements in the set , but this fact is in general not true for the preconditioner itself.

The fact that the - preconditioner contains the off-diagonal parts of the original matrix was used by Eisenstat [91] to derive at a more efficient implementation of preconditioned CG. This new implementation merges the application of the tridiagonal factors of the matrix and the preconditioner, thereby saving a substantial number of operations per iteration.



Jack Dongarra
Mon Nov 20 08:52:54 EST 1995