Suiv.: Résolution par décomposition de domaines Sup.: Résolution des systèmes linéaires Préc.: Résolution par une méthode directe Index Table des matières

Résolution par une méthode itérative

1.3.1 Introduction

Les méthodes présentées dans ce chapitre sont les méthodes classiques, de type gradient conjugué, pour la résolution d'un système linéaire. On distingue :

• la méthode classique du gradient conjugué préconditionnée   ou non, utilisable lorsque la matrice A du système linéaire à résoudre est symétrique définie positive  .  
• la méthode du double gradient conjugué   accélérée préconditionnée par factorisation incomplète   de la matrice A, dans le cas non symétrique  .

La première méthode est implémentée dans le code Modulef avec trois techniques de préconditionnement différentes. La matrice est stockée dans une structure de données de type AMAT.

La structure de données AMAT

Contenu

Cette SD permet de stocker les coefficients non nuls d'une matrice creuse carrée ou rectangulaire de type "éléments finis". Ce type de stockage est appelé morse ou compact.

La SD AMAT est composée de sept tableaux dont l'organisation est prédéfinie.

Tableau AMA0 : Informations générales.

De type entier, ce tableau possède 32 variables. Il contient une description générale du travail (titre, date, nom), de la SD AMAT  (type, niveau, ...) et indique la présence ou non du tableau AMA1.

1:20 TITRE

le titre du travail en 20 mots de 4 caractères (stockés dans des entiers),

21:22 DATE

la date de création en 2 mots de 4 caractères (idem),

23:28 NOMCRE

le nom du créateur en 6 mots de 4 caractères (idem),

29 'AMAT'

le type de la SD,

30 NIVEAU

le paramètre de niveau de la SD,

31 ETAT

un paramètre réservé,

32 NTACM

le nombre de tableaux supplémentaires associés à la SD
(ils seront décrits dans le tableau AMA1).

Tableau AMA1 : Descripteur des éventuels tableaux supplémentaires.

Ce tableau est analogue au tableau B1 de la SD B (voir cette SD).

Tableau AMA2 : Description générale de la matrice.

Ce tableau de type entier contient 10 valeurs.

1 NTDL

l'ordre de la matrice,

2 NTYP

le type des coefficients de la matrice,

3 NTCOEF

le nombre de coefficients a priori non nuls de la matrice,

4 NMO56

le nombre de mots nécessaires en mémoire centrale (M.C.) pour stocker les tableaux AMA5 et AMA6,

5 NPAGE

le nombre de pages de la matrice (si une mémoire secondaire est utilisée),

6 NCODSA

le type de stockage de la matrice avec :

• 1 : matrice symétrique, seule la partie triangulaire inférieure est stockée, ligne par ligne,
  
• 0 : matrice diagonale,
  
• -1 : matrice non symétrique, rangée ligne par ligne, le coefficient diagonal étant rangé en dernier,
  
• -l : matrice rectangulaire non symétrique, rangée ligne par ligne, de l lignes et NTDL colonnes,

7 ND

le nombre de degrés de liberté par noeud s'il est constant, 0 sinon,

8 NOE

le nombre de noeuds,

9 NMASMS

le nombre de matrices assemblées et stockées sur la M.S. (si 0 : AMA5 existe mais AMA6 n'existe pas),

10 NFACTO

le type de la factorisation de la matrice,
0 : aucune factorisation,
1 : factorisation complète ou non de Cholesky,
2 : factorisation complète ou non de Crout,

Tableau AMA3 : Pointeur sur la dernière ligne de chaque page.

Ce tableau, de type entier et de NPAGE + 1 mots, contient :

• AMA3(1) = 0,
• AMA3(i+1) = le numéro de la dernière ligne de la page i de la matrice,

Tableau AMA4  : Pointeur sur le coefficient diagonal de chaque ligne.

Ce tableau, de type entier et de NTDL + 1 (ou 2) mots, contient :

• si NCODSA = 0
  • AMA4(1) = 0
  • AMA4(2) = NTDL. Dans ce cas, le tableau AMA5 n'existe pas.
• si NCODSA = 1 ou -1
  • AMA4(1) = 0
  • AMA4(i+1) = le numéro du couple du coefficient diagonal (pointe donc sur AMA5 et AMA6)
• si NCODSA = -l
  • AMA4(1) = 0
  • AMA4(i+1) = le numéro du dernier coefficient de la ligne i.

Tableau AMA5  : Pointeur  sur les colonnes.

Ce tableau est de type entier et contient NTCOEF mots si NCODSA 0 et 0 mots sinon :

• AMA5(k) = numéro de la colonne du k-ème coefficient a priori non nul de la matrice,

Tableau AMA6 : Les coefficients de la matrice.

De type NTYP, ce tableau contient les NTCOEF coefficients non nuls de la matrice :

• AMA6(k) = valeur du k-ème coefficient non nul de la matrice,

Exemple 1 : Matrice diagonale en M.C.

On considère la matrice d'ordre 9 suivante (les valeurs sont les rangs dans le stockage et non les coefficients de la matrice) :

Alors, on a :

• NCODSA = 0
• le tableau AMA3 : (0 9)
• le tableau AMA4 : (0 9)
• le tableau AMA5 n'existe pas
• le tableau AMA6 :
  

Exemple 2 : Matrice symétrique en M.C.

On considère la matrice d'ordre 9 suivante (les valeurs sont les rangs dans le stockage et non les coefficients de la matrice) :

Alors, on a :

• NCODSA = 1
• le tableau AMA3 :
  

• le tableau AMA4 :
  

• le tableau AMA5 :
  

• le tableau AMA6 :
  
  

Les chaînages entre les tableaux AMA3, AMA4 et AMA5, donc la position des coefficients de la matrice dans le tableau AMA6 sont illustrés sur la figure 1.1.

 
Figure: Chaînages pour l'exemple 2 

Exemple 3 : Matrice non symétrique en M.C.

On considère la matrice d'ordre 9 suivante (les valeurs sont les rangs dans le stockage et non les coefficients de la matrice) :

Alors, on a :

• NCODSA = -1
• le tableau AMA3 :
  

• le tableau AMA4 :
  

• le tableau AMA5 :
  

• le tableau AMA6 :
  
  

Les chaînages entre les tableaux AMA3, AMA4 et AMA5, donc la position des coefficients de la matrice dans le tableau AMA6 sont illustrés sur la figure 1.2.

 
Figure: Chaînages pour l'exemple 3 

Dans le cas symétrique  , on stocke la matrice A dans un tableau monodimensionnel AMAT6  de la façon suivante : pour chaque ligne i, on ne garde que les coefficients non nuls, avec mc(i) j i( voir la description de la structure MUA pour la définition de mc(i)), rangés par indice de colonne j croissant. Ces lignes sont alors rangées par ordre croissant dans AMAT6. Pour gérer la correspondance entre AMAT6 et A, un pointeur AMAT4  est nécessaire, qui donne pour chaque ligne i l'adresse dans AMAT6 du dernier coefficient non nul . Enfin un pointeur AMAT5   de même taille que AMAT6, et rangé de manière cohérente donne pour chaque coefficient l'indice de colonne j correspondant. On ne stocke ainsi que les coefficients non nuls de la matrice A. L'adresse ia dans AMAT6 d'un coefficient quelconque n'est pas accessible directement, et il faut rechercher l'indice de colonne j dans AMAT5 entre les adresses AMAT4(i)+1 et AMAT4(i+1).

Dans le cas non symétrique  , on adopte la même forme de stockage, c'est-à-dire que l'on garde tous les coefficients non nuls de la ligne complète, en les rangeant par indice de colonne croissant, à l'exception du coefficient diagonal, placé en bout de ligne.

Ce mode de stockage est appelé stockage compact , dans Modulef il est aussi désigné sous le nom de stockage morse .