–

4 It was stated in Section 10.3.2 that for some speci¬c matrices the ILU(0) factorization of can

5

9

5 9

be put in the form

e

T £ RSP £ ¤ T £

¤

–

¤T T

in which and are the strict-lower and -upper parts of , respectively.

7¨

·§

”}$

8’

¨(c2 ¤ ¡" ¡©

©

$ ¥ © c"

©

&% Characterize these matrices carefully and give an interpretation with respect to their adja-

cency graphs.

&1 Verify that this is true for standard 5-point matrices associated with any domain .

&32 Is it true for 9-point matrices?

¢ & Is it true for the higher level ILU factorizations?

– T H BT

& &

5 Let be a pentadiagonal matrix having diagonals in offset positions . The

coef¬cients in these diagonals are all constants: for the main diagonal and -1 for all others. It ¡ –

is assumed that . Consider the ILU(0) factorization of as given in the form (10.20).

¦ ¥£¡ §

¤¢ £

The elements of the diagonal are determined by a recurrence of the form (10.19).

e ¡ ¨ § ! ©©§ ! X

&% Show that for .

¨§

&1 Show that is a decreasing sequence. [Hint: Use induction].

!

&32 Prove that the formal (in¬nite) sequence de¬ned by the recurrence converges. What is its

limit?

– £ ¢–

e £

0¤ T

T

6 Consider a matrix which is split in the form , where is a block diag-

– ¤T

onal matrix whose block-diagonal entries are the same as those of , and where is strictly

T

lower triangular and is strictly upper triangular. In some cases the block form of the ILU(0)

factorization can be put in the form (Section 10.3.2): 5

9

5 9

e

T £ $P £ ¤ T £

R

¤

£

The block entries of can be de¬ned by a simple matrix recurrence. Find this recurrence rela-

–

tion. The algorithm may be expressed in terms of the block entries the matrix .

7 Generalize the formulas developed at the end of Section 10.6.1 for the inverses of symmetric

tridiagonal matrices, to the nonsymmetric case.

8 Develop recurrence relations for Incomplete Cholesky with no ¬ll-in (IC(0)), for 5-point matri-

ces, similar to those seen in Section 10.3.4 for ILU(0). Same question for IC(1).

9 What becomes of the formulas seen in Section 10.3.4 in the case of a 7-point matrix (for three-

dimensional problems)? In particular, can the ILU(0) factorization be cast in the form (10.20) in

– –

¤T T

which is the strict-lower diagonal of and is the strict upper triangular part of , and

£

is a certain diagonal?

– e–

T¤T

£

10 Consider an arbitrary matrix which is split in the usual manner as , in which

–

¤T T

and are the strict-lower and -upper parts of , respectively, and de¬ne, for any diagonal

–

£

matrix , the approximate factorization of given by 5

9

5 9

e

T £ $P £ ¤ T £

R

¤

–

£ ¤

Show how a diagonal can be determined such that and have the same diagonal elements.

£

Find a recurrence relation for the elements of . Consider now the symmetric case and assume

£ ¤

that the matrix which is positive can be found. Write in the form 5 59 9

e

R £ R © £ © $P £ ¤ T © R £ © RSP £ ¤ T © R £

R

¤

95

C

What is the relation between this matrix and the matrix of the SSOR preconditioning, in the

" e " © $P £

R

particular case when ? Conclude that this form of ILU factorization is in effect an

SSOR preconditioning with a different relaxation factor for each equation. "

–

11 Consider a general sparse matrix (irregularly structured). We seek an approximate LU factor-

5

9

5 9

ization of the form

e

T £ $P £ ¤ T £

R

¤

p

¶ 8˜ H ˜ ¤ ¨°¡ $ H&’ ”8 ” &’ ¤ ©¦§

©8 $ $

£

¢ ¡¨ ¨¦ ¤

© §¥ c#&) $

©1

¢

¡

–

¤T T

in which and are the strict-lower and -upper parts of , respectively. It is assumed that

– is such that

e

§§ H

¢– § ¥ ¡ ¥ § ¡ H 0 ¡

'

for