to the original labeling. No additional work is required since the variables are already in

this form in the algorithm, but the variables must then be permuted at each preconditioning

¦

step. The second solution is to apply the permutation to all elements of as well as .

This does not require applying a permutation at each step, but rather produces a permuted

solution which must be permuted back at the end of the iteration phase. The complexity

of the ILUTP procedure is virtually identical to that of ILUT. A few additional options

¢ ±C

can be provided. A tolerance parameter called may be included to help determine

Y£

whether or not to permute variables: A nondiagonal element is candidate for a per- S

¯ ¢ ¡ ¡ ¡£

mutation only when . Furthermore, pivoting may be restricted to take

¡ S S ¡£

S

±

place only within diagonal blocks of a ¬xed size. The size of these blocks must be ¨

® ¨ f±

provided. A value of indicates that there are no restrictions on the pivoting.

For dif¬cult matrices, the following strategy seems to work well:

Always apply a scaling to all the rows (or columns) e.g., so that their -norms are

G

all equal to 1; then apply a scaling of the columns (or rows).

E E

“

Use a small drop tolerance (e.g., or .

ad

d

G¦ G

EH

¢ C

Take a large ¬ll-in parameter (e.g., ).

¡E

¡

± ¬

Do not take a small value for . Reasonable values are between and

¬ G E¬ E ¢ ¡E

, with being the best in many cases.

®¨ ±

Take unless there are reasons why a given block size is justi¬able.

¥

"0# ¥§¨

¢§ ©

Table 10.5 shows the results of applying the GMRES algorithm with

E

ILUTP(1% ) preconditioning to the ¬ve test problems described in Section 3.7. The

d

G

permtol parameter is set to 1.0 in this case.

Matrix Iters K¬‚ops Residual Error

F2DA 18 964 0.47E-03 0.41E-04

F3D 14 3414 0.11E-02 0.39E-03

ORS 6 341 0.13E+00 0.61E-04

F2DB 130 7167 0.45E-02 0.51E-03

FID 50 16224 0.17E+00 0.18E-03

¤ )0§ ¥¥©

¢ A test run of GMRES with ILUTP(1) precondi-

tioning.

See Example 6.1 for the meaning of the column headers in the table. The results are identi-

E

cal with those of ILUT(1% ) shown in Table 10.3, for the ¬rst four problems, but there

d

G

is an improvement for the ¬fth problem.

¦¦ !¥ !U 3

2 3¢6

2¡ 9 C@ T dHca Y

BP a9e

¡

The ILU preconditioners discussed so far are based mainly on the the IKJvariant of Gaus-

sian elimination. Different types of ILUs can be derived using other forms of Gaussian

p¶

·

’ gc ”8

˜© ˜ ªpv

88 8k10 ³

¡

¨¥ c© ¨ ¥£" Bc

$ ¡©

¢

¡

elimination. The main motivation for the version to be described next is that ILUT does

§

¦

¡

not take advantage of symmetry. If is symmetric, then the resulting is nonsym-

metric in general. Another motivation is that in many applications including computational

¬‚uid dynamics and structural engineering, the resulting matrices are stored in a sparse

skyline (SSK) format rather than the standard Compressed Sparse Row format.

sparse column

¤

sparse row

5"0# ¥ ¥£ ¥

§ ¢ § ¤¡

Illustration of the sparse skyline format.

In this format, the matrix is decomposed as

˜«

w w

¢

©

¨ f

%