4.3 M´ ethodes it´ eratives stationnaires et instationnaires
133
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
Fig. 4.3. La structure de matrice creuse de A est repr´ esent´ ee par des carr´ es, et celle
de R = A − LinUin, calcul´ ee par le Programme 17, par des points noirs
que R ait la mˆ eme structure que A, mais garantit que r ij = 0 si a ij = 0,
comme le montre la Figure 4.3.
On appelle ILU(0) la factorisation incompl` ete ainsi obtenue, o` u le “0”
signifie qu’aucun remplissage (fill-in) n’a ´ et´ e introduit pendant la factorisation. Une autre strat´ egie pourrait ˆ etre de fixer la structure de L in et
U in ind´ ependamment de celle de A, mais de mani` ere ` a satisfaire certains
crit` eres (par exemple, que les matrices obtenues aient la structure la plus
simple possible).
La pr´ ecision de la factorisation ILU(0) peut ˆ etre ´ evidemment am´ elior´ ee
en autorisant un peu de remplissage, c’est-` a-dire en acceptant qu’apparaissent des coefficients non nuls ` a certains endroits o` u les coefficients de
A ´ etaient nuls. Pour cela, on introduit une fonction, appel´ ee niveau de
remplissage, associ´ ee ` a chaque coefficient de A, et qui ´ evolue au cours de
la factorisation. Si le niveau de remplissage d’un coefficient d´ epasse une
valeur pr´ ealablement fix´ ee, le coefficient correspondant dans U in ou L in
est pris ´ egal ` a z´ ero.
Expliquons maintenant le principe du proc´ ed´ e quand les matrices L in et
U in sont progressivement ´ ecrites ` a la place de A (comme dans le Programme 4). Le niveau de remplissage d’un coefficient a
(k)
ij , not´ e lev ij –
pour fill-in level – (l’indice k ´ etant sous-entendu pour simplifier), est
cens´ e fournir une estimation raisonnable de la taille du coefficient durant la factorisation. On suppose en effet que si lev ij = q alors a ij δ
q
avec δ ∈]0, 1[, de sorte que q est d’autant plus grand que a
(k)
ij est petit.
Soit p ∈ N la valeur maximale du niveau de remplissage. Au d´ emarrage, le
niveau des coefficients non nuls et des coefficients diagonaux de A est fix´ e ` a
0, et le niveau des coefficients nuls est pris ´ egal ` a l’infini. Pour les lignes i =
133
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
Fig. 4.3. La structure de matrice creuse de A est repr´ esent´ ee par des carr´ es, et celle
de R = A − LinUin, calcul´ ee par le Programme 17, par des points noirs
que R ait la mˆ eme structure que A, mais garantit que r ij = 0 si a ij = 0,
comme le montre la Figure 4.3.
On appelle ILU(0) la factorisation incompl` ete ainsi obtenue, o` u le “0”
signifie qu’aucun remplissage (fill-in) n’a ´ et´ e introduit pendant la factorisation. Une autre strat´ egie pourrait ˆ etre de fixer la structure de L in et
U in ind´ ependamment de celle de A, mais de mani` ere ` a satisfaire certains
crit` eres (par exemple, que les matrices obtenues aient la structure la plus
simple possible).
La pr´ ecision de la factorisation ILU(0) peut ˆ etre ´ evidemment am´ elior´ ee
en autorisant un peu de remplissage, c’est-` a-dire en acceptant qu’apparaissent des coefficients non nuls ` a certains endroits o` u les coefficients de
A ´ etaient nuls. Pour cela, on introduit une fonction, appel´ ee niveau de
remplissage, associ´ ee ` a chaque coefficient de A, et qui ´ evolue au cours de
la factorisation. Si le niveau de remplissage d’un coefficient d´ epasse une
valeur pr´ ealablement fix´ ee, le coefficient correspondant dans U in ou L in
est pris ´ egal ` a z´ ero.
Expliquons maintenant le principe du proc´ ed´ e quand les matrices L in et
U in sont progressivement ´ ecrites ` a la place de A (comme dans le Programme 4). Le niveau de remplissage d’un coefficient a
(k)
ij , not´ e lev ij –
pour fill-in level – (l’indice k ´ etant sous-entendu pour simplifier), est
cens´ e fournir une estimation raisonnable de la taille du coefficient durant la factorisation. On suppose en effet que si lev ij = q alors a ij δ
q
avec δ ∈]0, 1[, de sorte que q est d’autant plus grand que a
(k)
ij est petit.
Soit p ∈ N la valeur maximale du niveau de remplissage. Au d´ emarrage, le
niveau des coefficients non nuls et des coefficients diagonaux de A est fix´ e ` a
0, et le niveau des coefficients nuls est pris ´ egal ` a l’infini. Pour les lignes i =