176
5 Systèmes linéaires
0
50
100
150
200
250
0
50
100
150
200
250
0
1
2
3
4
5
6
7
x 10
4
0
0.5
1
1.5
2
2.5
3
3.5
Figure 5.12. Structure de la matrice pour le premier cas test (à gauche),
et temps CPU (en sec.) nécessaire à la résolution du système linéaire associé
(à droite) : le trait plein correspond à la commande \, le trait mixte à la
factorisation de Cholesky, le trait discontinu à la méthode itérative PCG. Les
valeurs en abscisses correspondent à la dimension n de la matrice
avec précaution car elles sont dépendantes de l’implémentation et de
l’ordinateur utilisé.
Le cas d’une bande large
On considère à nouveau l’équation de Poisson, mais cette fois discrétisée par une méthode spectrale avec formules de quadrature de GaussLobatto-Legendre (voir par exemple [Qua09, CHQZ06]). La grille a autant de points que pour les différences finies, mais les méthodes spectrales
utilisent beaucoup plus de noeuds pour approcher les dérivées (en chaque
noeud, la dérivée selon x est approchée en utilisant tous les noeuds se
trouvant sur la même ligne ; de même, la dérivée selon y fait appel à tous
les noeuds se trouvant sur la même colonne). Les matrices résultantes
sont toujours creuses et structurées, mais ont beaucoup plus de coefficients non nuls que dans le cas précédent. On le voit sur l’exemple de la
Figure 5.13, à gauche, où la matrice spectrale a toujours N
2 = 256 lignes
et colonnes, mais cette fois-ci 7936 termes non nuls (au lieu de 1216 avec
la méthode des différences finies, Figure 5.12).
Le temps CPU indiqué sur la Figure 5.13, à droite, montre que, pour
cette matrice, l’algorithme PCG préconditionné par une factorisation
de Cholesky incomplète est beaucoup plus efficace que les deux autres
méthodes.
La conclusion de ce test est que pour les matrices symétriques définies positives à large bande, PCG est plus efficace que la méthode directe
implémentée dans MATLAB (qui n’utilise pas la factorisation de Cholesky, la matrice étant stockée en format sparse (creux)). Soulignons
qu’il est néanmoins crucial d’utiliser un bon préconditionneur pour que
la méthode PCG soit compétitive.
5 Systèmes linéaires
0
50
100
150
200
250
0
50
100
150
200
250
0
1
2
3
4
5
6
7
x 10
4
0
0.5
1
1.5
2
2.5
3
3.5
Figure 5.12. Structure de la matrice pour le premier cas test (à gauche),
et temps CPU (en sec.) nécessaire à la résolution du système linéaire associé
(à droite) : le trait plein correspond à la commande \, le trait mixte à la
factorisation de Cholesky, le trait discontinu à la méthode itérative PCG. Les
valeurs en abscisses correspondent à la dimension n de la matrice
avec précaution car elles sont dépendantes de l’implémentation et de
l’ordinateur utilisé.
Le cas d’une bande large
On considère à nouveau l’équation de Poisson, mais cette fois discrétisée par une méthode spectrale avec formules de quadrature de GaussLobatto-Legendre (voir par exemple [Qua09, CHQZ06]). La grille a autant de points que pour les différences finies, mais les méthodes spectrales
utilisent beaucoup plus de noeuds pour approcher les dérivées (en chaque
noeud, la dérivée selon x est approchée en utilisant tous les noeuds se
trouvant sur la même ligne ; de même, la dérivée selon y fait appel à tous
les noeuds se trouvant sur la même colonne). Les matrices résultantes
sont toujours creuses et structurées, mais ont beaucoup plus de coefficients non nuls que dans le cas précédent. On le voit sur l’exemple de la
Figure 5.13, à gauche, où la matrice spectrale a toujours N
2 = 256 lignes
et colonnes, mais cette fois-ci 7936 termes non nuls (au lieu de 1216 avec
la méthode des différences finies, Figure 5.12).
Le temps CPU indiqué sur la Figure 5.13, à droite, montre que, pour
cette matrice, l’algorithme PCG préconditionné par une factorisation
de Cholesky incomplète est beaucoup plus efficace que les deux autres
méthodes.
La conclusion de ce test est que pour les matrices symétriques définies positives à large bande, PCG est plus efficace que la méthode directe
implémentée dans MATLAB (qui n’utilise pas la factorisation de Cholesky, la matrice étant stockée en format sparse (creux)). Soulignons
qu’il est néanmoins crucial d’utiliser un bon préconditionneur pour que
la méthode PCG soit compétitive.