next up previous contents
Next: Méthodes itératives Up: Résolution du système algébrique Previous: Résolution du système algébrique

Méthodes directes

Il s'agit des méthodes utilisant la factorisation de la matrice représentant le système algébrique : ${\cal A} = {\cal L}.{\cal U}$. ${\cal L}$ et ${\cal U}$ sont respectivement des matrices triangulaires inférieures (lower) et supérieures (upper). Il y a donc deux étapes : la factorisation et la résolution. La factorisation est l'opération la plus couteuse. Elle peut par contre servir pour plusieurs résolutions si l'on ne change que le second membre.
La méthode de stockage utilisée s'appelle ligne de ciel (skyline profile). La ligne de ciel est définie par le niveau supérieur des colonnes au delà duquel il n'y a que des zéros. On ne stocke que la partie des colonnes situées sous le profil.

x x 0 x x 0 0 0 0
x x x x x x 0 0 0
0 x x 0 x x 0 0 0
x x 0 x x 0 x x 0
x x x x x x x x x
0 x x 0 x x 0 x x
0 0 0 x x 0 x x 0
0 0 0 x x x x x x
0 0 0 0 x x 0 x x


La ligne de ciel est toujours symétrique (si un noeud I est voisin du noeud J, alors J est voisin de I !). Il subsiste des zéros dans le stockage. On peut minimiser leur nombre en procédant à une renumérotation des noeuds à l'aide d'algorithmes de minimisation du stockage.
La manipulation d'une matrice stockée en ligne de ciel utilise un tableau, appelé profil, qui indique, pour chaque ligne, la position dans le stockage de son terme diagonal. L'assemblage s'écrit alors de la façon suivante :

pour chaque élément e
répéter j=1,nn
répéter i=1,nn
I=connec(i,e)
J=connec(j,e)
si J$\geq$I alors
irep = iprofil(J) - (J-I)
Aglobal(irep) = Aglobal(irep) + Alocal(i,j)
finsi
fin répéter
fin répéter


Lorsque le système n'est pas symétrique le stockage comprend deux parties, supérieure et inférieure, utilisant le même profil.
next up previous contents
Next: Méthodes itératives Up: Résolution du système algébrique Previous: Résolution du système algébrique
Marc Grandotto
2001-11-29