5.13 Pour finir : méthode directe ou itérative ?
175
des ressources informatiques disponibles (accès mémoire, processeurs rapides, etc.). Il faut reconnaître que nos tests sont biaisés par le fait qu’on
compare les méthodes directes implémentées dans la fonction \ de MATLAB, qui est compilée et optimisée, avec des méthodes itératives implémentées dans des fonctions qui ne sont ni compilées ni optimisées. Nos
calculs sont effectués sur un processeur Intel
R
Core
TM 2 Duo 2.53GHz
avec 3072KB de mémoire cache et 3GByte de mémoire vive.
Un système linéaire creux avec faible largeur de bande
Le premier cas test concerne les systèmes qu’on rencontre dans la discrétisation du problème de Poisson sur le carré ] − 1, 1[
2 , avec conditions
aux limites de Dirichlet homogènes, avec un schéma aux différences finies à 5 points (voir Section 8.2.4). On considère des grilles uniformes,
de pas h = 2/(N + 1) dans les deux directions de l’espace, pour diverses
valeurs de N . Les matrices correspondantes, à N
2 lignes et colonnes,
sont construites avec le Programme 8.2. Sur la Figure 5.12, à gauche,
on trace la structure de la matrice pour N
2 = 256 (avec la commande
spy) : la matrice est creuse, et elle a une structure bande, avec seule- spy
ment 5 termes non nuls par ligne. En éliminant les lignes et les colonnes
correspondant aux noeuds de la frontière, on obtient une matrice réduite
de taille n = (N − 1)
2 . Ces matrices sont symétriques définies positives
mais mal conditionnées : leur conditionnement spectral en fonction de
h se comporte comme une constante fois h
−2 . Autrement dit, plus le
paramètre h est petit, plus le conditionnement de la matrice se dégrade.
Pour résoudre les systèmes linéaires, on utilise la factorisation de Cholesky, le gradient conjugué préconditionné (PCG) par une factorisation
de Cholesky incomplète et la commande \ de MATLAB qui, dans le cas
présent, utilise un algorithme adapté aux matrices pentadiagonales symétriques. La factorisation incomplète de Cholesky est obtenue à partir
de manipulations algébriques des coefficients de la matrice R associée à
A (voir [QSS07]). On la calcule avec la commande cholinc(A,1.e-3). cholinc
Le critère d’arrêt pour PCG porte sur la norme du résidu relatif (5.60)
(qui doit être inférieure à 10
−13 ) ; le temps de calcul prend en compte le
temps nécessaire à la construction du préconditionneur.
Sur la Figure 5.12, à droite, on compare le temps de calcul (CPU)
pour les trois méthodes en fonction de la taille de la matrice. La méthode
directe qui se cache derrière la commande \ est de loin la plus rapide : elle
est basée sur une variante de l’élimination gaussienne particulièrement
efficace pour les matrices avec faible largeur de bande.
La méthode PCG est plus efficace que CG (sans préconditionnement).
Par exemple, si n = 3969 (ce qui correspond à N = 64) PCG ne requiert
que 18 itérations, alors que CG en nécessite 154. Les deux méthodes
sont cependant moins efficaces que la factorisation de Cholesky. Mais
nous mettons en garde le lecteur : ces conclusions doivent être prises
175
des ressources informatiques disponibles (accès mémoire, processeurs rapides, etc.). Il faut reconnaître que nos tests sont biaisés par le fait qu’on
compare les méthodes directes implémentées dans la fonction \ de MATLAB, qui est compilée et optimisée, avec des méthodes itératives implémentées dans des fonctions qui ne sont ni compilées ni optimisées. Nos
calculs sont effectués sur un processeur Intel
R
Core
TM 2 Duo 2.53GHz
avec 3072KB de mémoire cache et 3GByte de mémoire vive.
Un système linéaire creux avec faible largeur de bande
Le premier cas test concerne les systèmes qu’on rencontre dans la discrétisation du problème de Poisson sur le carré ] − 1, 1[
2 , avec conditions
aux limites de Dirichlet homogènes, avec un schéma aux différences finies à 5 points (voir Section 8.2.4). On considère des grilles uniformes,
de pas h = 2/(N + 1) dans les deux directions de l’espace, pour diverses
valeurs de N . Les matrices correspondantes, à N
2 lignes et colonnes,
sont construites avec le Programme 8.2. Sur la Figure 5.12, à gauche,
on trace la structure de la matrice pour N
2 = 256 (avec la commande
spy) : la matrice est creuse, et elle a une structure bande, avec seule- spy
ment 5 termes non nuls par ligne. En éliminant les lignes et les colonnes
correspondant aux noeuds de la frontière, on obtient une matrice réduite
de taille n = (N − 1)
2 . Ces matrices sont symétriques définies positives
mais mal conditionnées : leur conditionnement spectral en fonction de
h se comporte comme une constante fois h
−2 . Autrement dit, plus le
paramètre h est petit, plus le conditionnement de la matrice se dégrade.
Pour résoudre les systèmes linéaires, on utilise la factorisation de Cholesky, le gradient conjugué préconditionné (PCG) par une factorisation
de Cholesky incomplète et la commande \ de MATLAB qui, dans le cas
présent, utilise un algorithme adapté aux matrices pentadiagonales symétriques. La factorisation incomplète de Cholesky est obtenue à partir
de manipulations algébriques des coefficients de la matrice R associée à
A (voir [QSS07]). On la calcule avec la commande cholinc(A,1.e-3). cholinc
Le critère d’arrêt pour PCG porte sur la norme du résidu relatif (5.60)
(qui doit être inférieure à 10
−13 ) ; le temps de calcul prend en compte le
temps nécessaire à la construction du préconditionneur.
Sur la Figure 5.12, à droite, on compare le temps de calcul (CPU)
pour les trois méthodes en fonction de la taille de la matrice. La méthode
directe qui se cache derrière la commande \ est de loin la plus rapide : elle
est basée sur une variante de l’élimination gaussienne particulièrement
efficace pour les matrices avec faible largeur de bande.
La méthode PCG est plus efficace que CG (sans préconditionnement).
Par exemple, si n = 3969 (ce qui correspond à N = 64) PCG ne requiert
que 18 itérations, alors que CG en nécessite 154. Les deux méthodes
sont cependant moins efficaces que la factorisation de Cholesky. Mais
nous mettons en garde le lecteur : ces conclusions doivent être prises