Modulefpreviousupnextcontentsindex[BIG][Normal][small]
Suiv.: Résolution par une méthode itérative Sup.: Résolution des systèmes linéaires Préc.: 1.1 Introduction Index Table des matières


Résolution par une méthode directe

1.2.1 Introduction

Les méthodes présentées dans ce chapitre sont les trois méthodes classiques de résolution d'un système linéaire par factorisation  de la matrice. On distingue donc successivement :

Plusieurs versions de ces trois méthodes sont implémentées dans le code Modulef, suivant la place mémoire nécessaire au stockage de la matrice A.

Dans un premier temps, nous supposons que la matrice A peut être stockée intégralement en mémoire centrale, et nous décrivons précisément le stockage de la matrice et celui du second membre.

La structure de données MUA

 

Pour plus de détails consulter le [Guide Modulef - 2].

Contenu

Cette SD est l'organisation permettant de stocker, pour chaque ligne, les coefficients compris entre la première colonne de coefficient a priori non nul et la diagonale d'une matrice creuse de type "éléments finis". Ce type de stockage est dit profil ou skyline.

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

Tableau MUA0 : 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 MUA (type, niveau, ...) et indique la présence ou non du tableau MUA1.

1:20 TITRE

le titre du travail en 20 mots de 4 caractères,

21:22 DATE

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

23:28 NOMCRE

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

29 'MUA'

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 MUA1).

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

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

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

Ce tableau de type entier contient 12 valeurs.

1 NTYP

le type des coefficients de la matrice,

2 NBLOC

le nombre de blocs ou pages de la matrice,

3 NTCOL

le nombre de colonnes du plus grand bloc,

4 NMOPB

le nombre de mots nécessaires en m.c. pour stocker le plus grand bloc,

5 NMATA

le nombre de matrices sur le fichier,

6 NCODSA

le type de stockage de la matrice,

7 LBDP

la plus grande différence + 1 entre les numéros de 2 noeuds d'un même élément si NCODSA est non nul, 1 si NCODSA=0, c'est à dire la largeur de la demi-bande en terme de noeuds.

8 LBDPDL

la plus grande différence + 1 entre les numéros des degrés de liberté de 2 noeuds d'un même élément si NCODSA est non nul, 1 si NCODSA=0, c'est à dire et la demi-largeur de bande en terme de degrés de liberté.

9 ND

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

10 NOE

le nombre de noeuds,

11 NTDL

l'ordre de la matrice,

12 MUA5AR

l'assemblage est réalisé si 1, n'a pas déjà été fait si 0.

Tableau MUA3 : Pointeur sur le dernier degré de chaque bloc.

Ce tableau est de type entier, de longueur NBLOC+1, il contient :

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

Ce tableau est de type entier et de longueur NTDL+1 ou 2 selon NCODSA, il contient :

Tableau MUA5  : Les coefficients de la matrice.

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

Exemple 1 : Matrice symétrique

On considère la matrice d'ordre 12 suivante (les valeurs sont les rangs dans le stockage et non les coefficients de la matrice) formée de 3 pages :

Le tableau MUA5 de longueur MUA4(13) est subdivisé en 3 pages, ligne 1 à 5, 6 à 10 et 11 à 12. Chaque page a au plus 20 mots. Alors, on a :

Exemple 2 : Matrice non symétrique

On considère la matrice d'ordre 12 suivante (les valeurs sont les rangs dans le stockage et non les coefficients de la matrice) composée de 3 pages :

Ici, chaque page a au plus 13 mots. Alors, on a :

Dans le cas symétrique, on stocke la partie triangulaire inférieure de la matrice A dans un tableau monodimensionnel MUA5 , de la façon suivante : pour chaque variable i, on stocke tous les coefficients de la ligne, avec mc(i) j i, (où mc(i) est le plus petit indice de colonne tel que 0). Ces coefficients (nuls ou non) sont rangés par indice de colonne croissant. Les lignes sont ensuite rangées par ordre de variable croissant dans le tableau MUA5. Pour gérer la correspondance entre MUA5 et A, un pointeur MUA4  est nécessaire, qui donne pour chaque ligne i l'adresse dans MUA5 du coefficient diagonal . L'adresse ia dans MUA5 d'un coefficient quelconque est alors calculée par la formule ([note] Avec la convention MUA4(1)=0)

Ce mode de stockage appelé stockage profil ou skyline, est particulièrement commode puisqu'il est aussi utilisable pour la matrice L. En effet les matrices A et L ont le même profil, et dans la pratique on les stocke souvent dans le même tableau.

Dans le cas non symétrique , on utilise la même forme de stockage, en ajoutant les colonnes de la façon suivante : pour chaque variable i, on stocke tous les coefficients de la ligne, avec , (où mc(i) est le plus petit indice de colonne tel que ). Ces coefficients (nuls ou non) sont rangés par indice de colonne croissant; puis on stocke tous les coefficients de la colonne, avec mc(i) j i, en finissant par le coefficient diagonal. Ces informations sont ensuite rangées par ordre de variable croissant dans le tableau MUA5. Pour gérer la correspondance entre MUA5 et A, un pointeur MUA4 est nécessaire, qui donne pour chaque variable i l'adresse dans MUA5 du coefficient diagonal . L'adresse ia dans MUA5 d'un coefficient quelconque est alors calculée par la formule

La structure de données B

  Pour plus de détails consulter le [Guide Modulef - 2].

Contenu

Cette SD est l'organisation choisie pour stocker un tableau de coefficients ayant la structure d'un vecteur (second membre d'un système, solution, etc.).

En pratique, le tableau, noté B, est de la forme B(NDSM,NTDL) où NDSM désigne par exemple le nombre de cas de charge ou de seconds membres et NTDL le nombre de degrés de liberté.

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

Tableau B0 : 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 B (type, niveau, ...) et indique la présence ou non du tableau B1.

1:20 TITRE

le titre du travail en 20 mots de 4 caractères,

21:22 DATE

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

23:28 NOMCRE

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

29 'B '

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 B1).

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

Ce tableau de type entier existe si NTACM (cf. B0) est non nul. Il contient, pour chaque tableau à décrire, 22 variables. En règle générale, il n'y a pas de tableaux associés sauf pour certaines applications où l'on a besoin de conserver dans la SD des valeurs n'entrant pas dans le cadre de sa définition standard.

Si le tableau B1 existe, il contient séquentiellement :

Boucle i de 1 à NTACM

Fin de boucle.

Tableau B2 : Description générale du tableau de coefficients.

Ce tableau de type entier contient 11 valeurs.

1 NTYP

le type du tableau B4,

2 NIND

le nombre de ses indices (fixé à 2),

3 M1

la valeur maximale de son premier indice (par exemple NDSM  , le nombre de cas de charge),

4 M2

la valeur maximale de son second indice (par exemple NTDL si B4 n'a qu'une page),

5 NCOD

le code de découpage en blocs du tableau B4 avec :

6 NBLOC

le nombre de blocs,

7 NOE

le nombre de noeuds,

8 NBBLOC

le nombre de tableaux B4 lorsque la SD est sur fichier,

9 ND

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

10 NTDL

le nombre de degrés de liberté ou la valeur maximale du second indice du tableau B4 lorsque les NBLOC blocs sont considérés,

11 NCODSB

le code de stockage du tableau B4 avec :

Tableau B3 : Pointeur sur les blocs.

Ce tableau de type entier contient NBLOC+1 variables indiquant la segmentation du tableau B4.

Tableau B4  : Les coefficients du(des) tableau(x).

De type NTYP ce tableau contient les NDSM*M2 valeurs de chaque page.

B4(1,l+1) à B4(NDSM,l+1) puis
B4(1,l+2) à B4(NDSM,l+2) puis
....
B4(1,l) à B4(NDSM, ).

pour l = NDL(B3(i)+1) et = NDL(B3(i+1)+1) où NDL est le nombre de degrés de liberté par noeuds.

Cet ensemble de 5 tableaux (B0, B1, B2, B3 et B4) gérés par quelques sous-programmes, contient les NDSM seconds membres (ou les solutions) d'un système linéaire A x = b. Les coefficients du tableau B4(NDSM,NTDL) représentent les NTDL   composantes des NDSM  seconds membres du système linéaire à résoudre. Après résolution, les solutions du système linéaire sont aussi rangés dans un tableau B4 (le même, ou celui d'une structure B distincte).


Modulefpreviousupnextcontentsindex[BIG][Normal][small]
Suiv.: Résolution par une méthode itérative Sup.: Résolution des systèmes linéaires Préc.: 1.1 Introduction Index Table des matières