2. Renumérotation et factorisation symbolique : MLTPRE#
Par commodité, on a omis le préfixe NU, devant les noms de structure.
Structures de données lues .
De la structure de données: nume_ddl, on extrait les enregistrements:
NUME.DELG: indique si le degré de liberté est de «Lagrange» ou non.
NUME.DEEQ,
NUME.NUEQ,
NUME.PRNO: Ces 3 enregistrements établissent les liens entre les degrés de liberté soumis à une condition aux limites et les Lagranges correspondant.
Les 3 enregistrements suivants décrivent une matrice «Morse».
SMOS.SMHC: Numéro de colonne du terme
SMOS.SMDI: Adresses des termes diagonaux
SMOS.SMDE.: Nombres d’inconnues, et de termes de la matrice
Structures de données écrites.
(En face de chaque structure Code_Aster , on a écrit le nom du tableau FORTRAN correspondant, qui sera utilisé, par la suite pour plus de commodités.)
MLTF.ADNT ADINIT: adresses des termes initiaux dans la matrice factorisée
MLTF.LGBL LGBLOC: longueur des blocs de la matrice factorisée
MLTF.LGSN LGSN: longueur des super-nœuds
MLTF.LOCL LOCAL: utilisé dans l’assemblage des matrices frontales, correspondance entre les numéros locaux du super-nœuds père et fils.
MLTF.ADRE ADRESS
MLTF.SUPN SUPND: définition des super-nœuds
MLTF.FILS FILS: fils des super-nœuds dans l’arbre d’élimination
MLTF.FRER FRERE: frère des super-nœuds dans l’arbre d’élimination
MLTF.LGSN LGSN: longueur des super-nœuds
MLTF.LFRN LFRONT: ordre des matrices frontales (après élimination)
MLTF.NBAS NBASS: pointeur lié à l’assemblage des matrices frontales
MLTF.ADPI ADPILE: adresses dans la pile des matrices frontales
MLTF.ANCI ANC: tableau inverse de la renumérotation
MLTF.NBLI NBLIGN: ordre des matrices frontales (avant élimination)
MLTF.NCBL NCBLOC: nombre de degrés de liberté de chaque bloc
MLTF.DECA DECAL: décalage entre le début de colonne d‘un super-nœud et le début du bloc JEVEUX qui le contient
MLTF.SEQU SEQ: ordre d’élimination des super-nœuds (parcours de l’arborescence).
Ces structures de données seront décrites dans les paragraphes suivants.
Description du code.
On distingue 2 phases, la première consiste en la renumérotation, la seconde en ce que l’on appelle dans le langage de la méthode multi-frontale, la factorisation symbolique.
La structure de données NUME_DDL décrit une numérotation des \(\text{NEQ}\) degrés de liberté, comprenant, la plupart du temps, des degrés de liberté dits de Lagrange. Ces degrés de liberté doivent satisfaire la relation d’ordre suivante:
\(\mathit{L1}<U<\mathit{L2}\) , si \(\mathit{L1}\) et \(\mathit{L2}\) sont les «Lagranges» associés à la condition aux limites sur \(U\) .
Afin de conserver cet ordre, on va soumettre à l’algorithme de renumérotation uniquement les degrés de liberté non «Lagranges». Les degrés de liberté «Lagranges sont donc ôtés et les informations les concernant sont stockées afin de les réintégrer dans la nouvelle numérotation, tout en satisfaisant (1).
Routines appelées (un première description succincte du code).
Pour la première phase, les routines appelées sont les suivantes:
PREML0: extraction des informations sur les «Lagranges»
PREMLA: traitement pour les «Lagranges» de type relation linéaire
PREML1: pré traitement et renumérotation.
PREMLC : post-traitement de la renumérotation (ajout des «Lagranges»).
PREMLD: idem
Pour la seconde:
PREML2: factorisation symbolique.
2.1. PREML0#
On stocke dans les tableaux \(\mathit{LBD1}\) , \(\mathit{LBD2}\) , les «Lagranges» de blocage, et dans \(\mathit{RL}\) les «Lagranges» de relation linéaire.
On obtient une nouvelle numérotation de \(1\) à \(\mathit{N2}\) des degrés de liberté sans Lagrange, définie par:
\(P\) de \([1:\text{NEQ}]\mathrm{\Rightarrow }[1-\mathit{N2}]\) , et \(Q\) Inverse de \(P\) .
Pour \(I\) de \(1\) à \(\text{NEQ}\) , si \(I\) est un degré de liberté bloqué, \(\mathit{LBD1}(I)\) , (resp. \(\mathit{LBD2}(I)\) ), est le numéro de son L1 (resp. \(\mathit{L2}\) ).
Dans le cas de \(\mathit{NRL}\) relations linéaires, on aura:
\(\mathit{RL}(1,I)\) : \(\mathit{L1}\) de la relation \(I\) ,
\(\mathit{RL}(2,I)\) : \(\mathit{L2}\) de la relation \(I\) .
N.B. Programmation
Dans certaines routines, on utilisera le nom de variable \(\mathit{N1}\) en place de \(\text{NEQ}\) .
2.2. PREMLA#
Pour tous les degrés de liberté \(\mathit{L2}\) de relation linéaire, (second «Lagrange»), ses voisins de numéro inférieur sont connus en extrayant l’information de la structure de données SMOS.SMHC (tableau COL).
A partir de ces informations, PREMLAcrée des listes chaînées (tableaux DEB, VOIS, SUIT) pour les degrés de liberté de relation linéaire \(\mathit{L2}\) .
Soit \(J\) un degré de liberté inclus dans une relation linéaire, \(\mathit{j0}=\mathit{DEB}(j)\) est l’adresse du premier voisin de \(J\) dans le tableau \(\mathit{VOIS}\) , \(\mathit{J1}=\mathit{SUIV}(\mathit{J0})\) est l’adresse du voisin suivant, \(\mathit{J2}=\mathit{SUIV}(\mathit{J1})\) est l’adresse du suivant et ainsi de suite.
Cette liste chaînée sera utilisée par la suite dans PREML1, pour la fabrication de \(\mathit{ADJNCY}\) .
N.B. Allocation de mémoire
La liste chaînée consiste en 2 structures locales, de noms NOMVOI et NOMSUI , (créées par WKVECT et détruites en fin de MLTPRE ).
Leur longueur: \(\mathit{LGLIST}\) , est estimée a priori par PREML0 (paramètre de sortie \(\text{LT}\) ), s’il est insuffisant, PREMLA fournit un code d’erreur, et est appelé de nouveau avec des structures de longueur 2 fois plus grandes.
2.3. PREML1#
PREML1 appelle les routines suivantes:
PRMADJ, GENMMD, AMDBAR, ONMETL.
Le rôle essentiel de PREML1 est de lancer la renumérotation. Celle-ci, effectuée au choix par: METIS (méthode de dissection), GENMMD (minimum degree) ou AMDBAR (minimum degree amélioré), nécessite 2 actions préalables.
2.3.1. Reconstitution des nœuds (au sens de la discrétisation par éléments finis).#
Dans une première version du code, l’algorithme de renumérotation travaillait sur les \(\mathit{N2}\) degrés de liberté (sans Lagranges).
On a voulu ensuite préserver l’ordre interne des inconnues au sein des nœuds de discrétisation élément finis (par exemple \(\mathit{ux}\) , \(\mathit{uy}\) , \(\mathit{uz}\) , \(p\) ).
Un développement a été effectué à cet effet. On soumet désormais à l’algorithme de renumérotation l’ensemble des nœuds et non les \(\mathit{N2}\) degrés de liberté .
On forme donc un nouvel ensemble de \(\mathit{NBND}\) nœuds et 2 pointeurs associés:
\(\mathit{NŒUD}[\mathrm{1 }:\mathit{N2}]\mathrm{\Rightarrow }[\mathrm{1 }:\mathit{NBND}]\) , et le pointeur inverse \(\mathit{DDL}[\mathrm{1 }:\mathit{NBND}]\)
On a ainsi 3 numérotations:
Numérotation initiale de \(1\) à \(\text{NEQ}\) ,
Celle des degrés de liberté sans Lagranges \(1\) à \(\mathit{N2}\) ,
Celle des nœuds d’interpolation \(1\) à \(\mathit{NBND}\) .
Munies des tableaux \(P\) et \(Q\) entre la première et le deuxième, \(\mathit{NŒUD}\) et \(\mathit{DDL}\) entre la deuxième et la troisième.
2.3.2. Création de la structure (\(\mathit{ADJNCY}\),:math:mathit{XADJ})#
Cette structure est la structure standard de données des algorithmes de renumérotation cités plus haut. On a 2 tableaux \(\mathit{ADJNCY}\) et \(\mathit{XADJ}\) définis comme suit:
Soit un nœud \(I\) , ses voisins se trouvent stockés dans le tableau \(\mathit{ADJNCY}\) , entre les adresses \(\mathit{XADJ}(I)+1\) et \(\mathit{XADJ}(I+1)\) .
On crée d’abord une structure \((\mathit{ADJNCY},\mathit{XADJ})\) relative aux \(\mathit{N2}\) degrés de liberté, puis la routine PRMADJ la transforme en une structure \((\mathit{ADJNCY},\mathit{XADJD})\) relative aux \(\mathit{NBND}\) nœuds.
Pour créer \(\mathit{ADJNCY}\) , on utilise la liste chaînée \((\mathit{DEB},\mathit{VOIS},\mathit{SUIT})\) créée par PREMLA, en forçant les degrés de liberté d’une relation linéaire à être voisins. Ainsi ces degrés de liberté seront dans le même super nœud, de même que leur \(\mathit{L2}\) . La relation d’ordre sera ainsi respectée.
On effectue ensuite l’appel à GENMMD, AMDBAR ou METIS. On obtient les résultats habituels de cet algorithme:
Renumérotation,
Définition des super-nœuds,
Arborescence
Les sources de ces 3 méthodes sont dans le domaine public.
Concernant les 2 derniers points, il a fallu les adapter. La renumérotation concerne les nœuds (\(1\) à \(\mathit{NBND}\) ), elle a la forme de 2 tableauxinverses l’un de l’autre: \(\mathit{INVPND}\) , \(\mathit{PERMND}\) . (\(\mathit{INVPND}(I)\) est le nouveau numéro du nœud \(I\) ).
L’arborescence, quant à elle, porte sur les super-nœuds créés par la renumérotation. Le super-nœud \(\mathit{SND}\) est défini comme suit: il est constitué du segment de nœuds \([\mathit{SPNDND}(\mathit{SND}-1)+1,\mathit{SPNDND}(\mathit{SND})]\) . \(\mathit{SPNDND}\) est ainsi une injection du segment \([\mathrm{1 }:\mathit{NBSND}]\) vers \([\mathrm{1 }:\mathit{NBND}]\) , \(\mathit{NBSND}\) : nombre de super-nœuds.
L’arborescence est définie comme suit: \(\mathit{PARENT}(\mathit{SND})\) est le nœud «père» du super-nœud \(\mathit{SND}\) .
N.B. Programmation
L’arborescence des super-nœuds de la multi-frontale, apparaît sous 2 noms: \(\mathit{PARENT}\) et \(\mathit{PAREND}\)
Le premier contient l’arborescence des SN hors Lagrange, il est fourni par la renumérotation ( GENMMD/AMDBAR/METIS .)
Le second est le complété du premier en y ajoutant les Lagranges, il est calculé par PREMLC à partir du premier.
Dans le programme appelant MLTPRE, \(\mathit{PARENT}\) , qui est un intermédiaire, est stocké dans \(\mathit{ZI}\) à l’adresse \(\mathit{SEQ}\) , réutilisé plus tard (gain de place).
Ces tableaux précédents sont définis en fonctions des \(\mathit{NBND}\) nœuds de discrétisation de Code_Aster , (\(1\) à \(\mathit{NBND}\) ). Ils sont reconstruits ensuite dans la numérotation des \(\mathit{N2}\) degrés de liberté non «Lagrange».
\(\mathit{INVPND}\) devient ainsi \(\mathit{INVP}\) , \(\mathit{PERMND}\) devient \(\mathit{PERM}\) et \(\mathit{SPNDND}\) devient \(\mathit{SUPND}\) . (Cf. boucles 400 405 406 407 de PREML1).
N.B. Allocation de mémoire
La structure \((\mathit{XADJ},\mathit{ADJNCY})\) de PREML1 , est appelée \((\mathit{XADJ2},\mathit{ADJNC2})\) dans MLTPRE *. Elle est créée avant* PREML1 et détruite après. La longueur de \(\mathit{ADJNC2}\) , \(\mathit{LGADJN}\) , est estimée à \(2\times (\mathit{lmat}-neq+\mathit{lglist})\) , avec \(\mathit{lglist}\) = longueur de la liste des voisins utilisée dans PREML0
\(\mathit{lmat}\) = longueur de la matrice initiale (fournie par SMOS ).
Si \(\mathit{LGADJN}\) est insuffisant, PREML1 fournit la longueur nécessaire en code retour, et est relancé.
NB. METIS
Auparavant, on produisait un exécutable du logiciel METIS , écrit en C, compilé et linké séparément. Cet exécutable était appelé à travers APLEXT , couche d’appel d’un exécutable externe par Code_Aster. Désormais les routines de METIS sont compilées et appelées par un appel à ONMETL , fonction C appelante.
2.4. PREMLC#
En sortie de PREML1, les résultats sont exprimés en terme de degrés de liberté non «Lagrange» (\(1\) à \(\mathit{N2}\) ), la routine PREMLC complète la numérotation de \(1\) à \(\mathit{N2}\) en ajoutant les «Lagrange» et en créant de nouveaux super-nœuds.
Les «Lagrange» sont inclus ainsi dans la nouvelle numérotation:
Pour chaque \(\mathit{L1}\) , on crée un nouveau super-nœud \(\mathit{SN}\) , constitué d’un seul degré de liberté (\(\mathit{L1}\) ), et fils du premier degrés de liberté dont il est le «Lagrange» (bloqué ou relation linéaire). En étant le fils de ce degré de liberté, il sera éliminé auparavant, ce qui est la règle.
Pour les \(\mathit{L2}\) , on ne crée pas de nouveau \(\mathit{SN}\) , on se contente d’ajouter un degré de liberté supplémentaire (\(\mathit{L2}\) ) au super-nœud contenant le degré de liberté (bloqué ou R.L.) dont il est le «Lagrange».
En cas de relation linéaire, tous les degrés de liberté de la relation sont mis par l’algorithme dans le même super-nœud. Cela est réalisé dans le paragraphe précédent (PREML1), lors de la fabrication de la structure \(\mathit{ADJNCY}\) , en forçant les degrés de liberté des relations linéaires à être voisins entre eux, au moyen de la liste chaînée (\(\mathit{DEB}\) , \(\mathit{VOIS}\) , \(\mathit{SUIV}\) ).
On obtient les nouvelles renumérotations \(\mathit{NOUV}\) et \(\mathit{ANC}\) sur \([1:\text{NEQ}]\) , pour tous les degrés de liberté dans la nouvelle numérotation, \(\mathit{ANC}(I)\) fournira son numéro dans la numérotation initiale. \(\mathit{NOUV}\) est le tableau inverse.
\(\mathit{NBSN}\) le nouveau nombre de super-nœuds et \(\mathit{SUPND}[1:\mathit{nbsnd}+1]\) définit ces \(\mathit{SN}\) .
Le super-nœud \(\mathit{SN}\) est constitué du segment de nœuds \([\mathit{SUPND}(\mathit{SN}-1)+1,\mathit{SUPND}(\mathit{SN})]\) .
\(\mathit{SUPND}\) est ainsi une application du segment \([\mathrm{1 }:\mathit{NBSN}]\) vers \([\mathrm{1 }:\text{NEQ}]\) .
N.B. Allocation de mémoire
\(\mathit{LGIND}\) est la longueur estimée des tableaux \(\mathit{GLOBAL}\) ET \(\mathit{LOCAL}\) , (Cf. plus loin 2.6 ) qui sont alloués avant PREML2( \(\mathit{NOPGLO}\) et \(\mathit{NOPLOC}\) )
\(\mathit{LGIND}\) est d’abord un résultat de la renumérotation, fourni par PREML1 et augmenté par PREMLC en fonction des conditions aux limites.
\(\mathit{LGIND}\) est une surestimation de \(\mathit{GLOBAL}\) et \(\mathit{LOCAL}\) on ne veut pas conserver une structure trop importante.
Ainsi, après PREML2 , on connaît la longueur réelle de ces tableaux, on redéfinit \(\mathit{LGIND}\) à cette valeur, et on recopie \(\mathit{GLOBAL}\) et \(\mathit{LOCAL}\) dans des structures \(\mathit{NOMGLO}\) et \(\mathit{NOMLOC}\) de longueur exacte.
2.5. PREMLD#
C’est une étape technique: cette routine fabrique une structure de type \(\mathit{ADJNCY}\) comme celles utilisées par les algorithmes de renumérotation, cette fois-ci tous les degrés de liberté de \(1\) à \(\text{NEQ}\) sont pris en compte.
N.B. Allocation de mémoire
La structure \((\mathit{XADJ},\mathit{ADJNCY})\) fabriquée par PREMLD , est appelée \((\mathit{XADJ1},\mathit{ADJNC1})\) dans MLTPRE *.*
On utilise la même longueur \(\mathit{LGADJN}\) calculée précédemment .
2.6. PREML2#
C’est la seconde phase de MLTPRE: on effectue entre autres, la factorisation symbolique qui est une simulation de la factorisation réelle, sans opération flottante, destinée à faciliter le travail de la factorisation réelle, en fabriquant certains pointeurs nécessaires.
PREML2 appelle les routines suivantes:
FACSMB: factorisation symbolique proprement dite.
MLTPOS : fabrication de la séquence de factorisation, c’est à dire, remontée de l’arborescence définie par le tableau \(\mathit{PAREND}\) , qui définit ainsi l’ordre d’élimination des super-nœuds.
MLTBLC : On définit ici le découpage en blocs de la matrice factorisée, virtuellement «out of core», car découpée en blocs libérables par le progiciel JEVEUX.
MLTPAS : On calcule ici l’adresse des coefficients initiaux dans la matrice factorisée.
2.6.1. FACSMB#
Données (Elles sont issues de la renumérotation):
\(\mathit{SUPND}\)
\(\mathit{PAREND}\) ,
(Et de la topologie initiale):
\(\mathit{ADJNCY}\) .
Résultats :
\(\mathit{GLOBAL}\)
\(\mathit{LOCAL}\)
\(\mathit{ADRESS}\)
\(\mathit{NBASS}\)
\(\mathit{DEBFAC}\)
\(\mathit{DEBFSN}\)
\(\mathit{LGSN}\)
\(\mathit{LFRON}\)
\(\mathit{FILS}\)
\(\mathit{FRERE}\) .
Ces tableaux sont décrits ci-dessous.
\(\mathit{FILS}\) et \(\mathit{FRERE}\) sont les tableaux «inverse» du tableau \(\mathit{PAREND}\) , ils permettent de connaître tous les super-nœuds «fils» d’un super-nœud donné \(\mathit{SN}\) , ce sont \(\mathit{FILS}(\mathit{SN})\) , \(\mathit{FRERE}(\mathit{FILS}(\mathit{SN}))\) , et ainsi de suite. Pour les autres résultats, il est nécessaire de revenir sur les principes de base de la méthode multi-frontale, au moyen des figures suivantes:
|
Figure 1 Assemblage de 2 matrices filles dans une matrice mère
|
Figure 2 Matrice frontale \(\mathit{SN}\)
On voit sur la Figure 1, la matrice frontale \(\mathit{SN}\) (du super-nœud \(\mathit{SN}\) ), constituée des termes provenant de la matrice initiale, ainsi que des termes provenant des matrices filles \(\mathit{SNF1}\) et SNF2, après élimination des super-nœuds \(\mathit{SNF1}\) et \(\mathit{SNF2}\) . Après élimination, la partie grisée de la matrice frontale va constituer les colonnes de la matrice factorisée, et la partie blanche restante rangée dans la pile des matrices frontales, ira s’agglomérer à la matrice mère lors de l’assemblage de cette dernière.
La factorisation symbolique effectuée par FACSMB va simuler ce processus d’assemblage/élimination. Pour chaque super-nœud \(\mathit{SN}\) , on va fabriquer une liste chaînée contenant les numéros d’inconnues du super nœud lui-même, ainsi que les numéros d’inconnues des voisins de tous les fils de \(\mathit{SN}\) . On inclut les voisins des fils, mais non les fils eux-mêmes qui ont été éliminés.
En langage FORTRAN, FACSMB produit les tableaux suivants:
\(\mathit{LGSN}(\mathit{SN})\) : nombre d’inconnues du super-nœud \(\mathit{SN}\) (en fait = \(\mathit{supnd}(\mathit{sn}+1)-\mathit{supnd}(\mathit{sn})\) ),
\(\mathit{NBLIGN}(\mathit{SN})\) : nombre d’inconnues total de la matrice frontale SN
\(\mathit{LFRONT}(\mathit{SN})=\mathit{NBLIGN}(\mathit{SN})-\mathit{LGSN}(\mathit{SN})\) , ordre de la matrice frontale après élimination qui sera stockée dans la pile.
FACSMB fabrique aussi un tableau \(\mathit{GLOBAL}\) , muni d’un tableau de pointeurs \(\mathit{ADRESS}\) .
\(\mathit{GLOBAL}\) contient les numéros des inconnues de la matrice frontale \(\mathit{SN}\) (avant élimination), entre les adresses \(\mathit{ADRESS}(\mathit{SN})\) et \(\mathit{ADRESS}(\mathit{SN}+1)-1\) .
Ces inconnues sont au nombre de \(\mathit{NBLIGN}(\mathit{SN})=(\mathit{ADRESS}(\mathit{SN}+1)-\mathit{ADRESS}(\mathit{SN}))\) .
On accède au tableau \(\mathit{LOCAL}\) comme \(\mathit{GLOBAL}\) , au moyen du tableau \(\mathit{ADRESS}\) . Soit \(\mathit{FSN1}\) le super-nœud «fils» du super-nœud \(\mathit{SN}\) , comme sur la figure ci-dessus, et soit \(I\) un indice compris entre \(\mathit{ADRESS}(\mathit{FSN1})+\mathit{LGSN}(\mathit{FSN1})\) et \(\mathit{ADRESS}(\mathit{FSN1}+1),\mathit{LOCAL}(I)\) sera le numéro local (compris entre \(1\) et \(\mathit{NBLIGN}(\mathit{SN})\) ) de cette inconnue dans la matrice du super-nœud «père» \(\mathit{SN}\) (on a \(\mathit{PAREND}(\mathit{FSN1})=\mathit{SN}\) ).
\(\mathit{LOCAL}\) sera utilisé dans l’assemblage de la matrice frontale «fille» dans la matrice frontale «mère», il donne directement l’adresse de destination. On illustre ceci à l’aide de l’exemple suivant:
|
La matrice frontale \(\mathit{SN}\) a \((p+q)\) inconnues: \(\mathit{i1},\mathit{i2},\mathrm{..},\mathit{ip},\mathit{e1},\mathit{e2},\dots ,\mathit{eq}\) , avec
\(\mathit{NBLIGN}(\mathit{SN})=p+q\)
\(\mathit{LGSN}(\mathit{SN})=p\)
\(\mathit{LFRONT}(\mathit{SN})=q\)
\(\mathit{ADRESS}(\mathit{SN}+1)–\mathit{ADRESS}(\mathit{SN})=p+q\) ,
\(\mathit{GLOBAL}=[\mathit{i1},\mathit{i2},\dots \mathit{ip},\mathit{e1},\mathit{e2},\dots \mathrm{..}\mathit{eq}]\) , aux adresses variant entre \(\mathit{ADRESS}(\mathit{SN})+1\) et \(\mathit{ADRESS}(\mathit{SN}+1)\) ,
\(\mathit{LOCAL}=[0,0,\mathrm{..},0,\mathit{l1},\mathit{l2},\dots \dots .\mathit{lq}]\)
Aux mêmes adresses que ci-dessus, \(\mathit{l1},\mathit{l2},\mathit{lq}\) sont les numéros locaux dans la matrice frontale de \(\mathit{PAREND}(\mathit{SN})\) .(valeurs comprises entre \(1\) et \(\mathit{NBLIGN}(\mathit{PAREND}(\mathit{SN}))\) ).
\(\mathit{NBASS}\) , compteur utilisé lui aussi pour l’assemblage, est défini ainsi: \(\mathit{NBASS}(\mathit{FSN1})\) est le nombre d’inconnues \(\mathit{INC}\) tel que \(\mathit{INC}<\mathit{SUPND}(\mathit{SN}+1)\) , où \(\mathit{PAREND}(\mathit{FSN1})=\mathit{SN}\) . C’est donc le nombre d’inconnues de \(\mathit{FSN1}\) , assemblées dans la matrice mère \(\mathit{SN}\) et qui seront éliminées lors de l’élimination de \(\mathit{SN}\) .
\(\mathit{DEBFAC}\) et \(\mathit{DEBFSN}\) , ces 2 tableaux donnent les mêmes valeurs, le premier est indicé par inconnue, le second par super-nœud, ils fournissent, pour \(\mathit{DEBFAC}\) , les adresses des coefficients diagonaux des inconnues dans la matrice factorisée. Pour \(\mathit{DEBFSN}\) , il s’agit de l’adresse du coefficient diagonal de la première inconnue du super-nœud.
On a vu sur la Figure 2, que les colonnes correspondant aux inconnues du super-nœud éliminé, (en grisé), constituaient les colonnes de la matrice factorisée que l’on appelle \(\mathit{FACTOR}\) . Les adresses des coefficients diagonaux fournies par DEBFAC sont des adresses dans un tableau virtuel \(\mathit{FACTOR}\) contenant la matrice factorisée. En fait un ensemble de blocs JEVEUX contiendra la matrice factorisée, et on maniera un pointeur supplémentaire pour chaque bloc.
N.B. Programmation
On voit sur les figures précédentes que l’on stocke les colonnes du \(\mathit{SN}\) , toutes entières, (rectangle grisé), sans prendre en compte la symétrie du bloc diagonal. On consomme ainsi un peu plus de mémoire, mais on a affaire à un stockage régulier nécessaire à l’utilisation des routines BLAS qui demandent des stockages dans des tableaux FORTRAN à 2 dimensions.
2.6.2. MLTPOS#
On rappelle que les matrices frontales issues des éliminations sont stockées dans une pile. Toutes les matrices filles d’un même super nœud \(\mathit{SN}\) sont stockées (empilées), consécutivement. Une fois lues (dépilées), elles ne sont plus réutilisées, et la matrice frontale issue de l’élimination de \(\mathit{SN}\) est stockée à leur place. La longueur de cette pile diminue ou augmente au fil des éliminations, Elle atteint un maximum qu’il est nécessaire de connaître.
MLTPOS parcourt l’arborescence, calcule \(\mathit{ESTIM}\) , longueur maximum de la pile pour son allocation ultérieure, construit un tableau \(\mathit{SEQ}(\mathrm{1 }:\mathit{NBSN})\) qui fournit l’ordre d’élimination des super-nœuds en parcourant de bas en haut l’arborescence. Il fournit \(\mathit{ADPILE}\) qui contient l’adresse dans la pile des matrices frontales des \(\mathit{SN}\) .
MLTPOS contient un algorithme de renumérotation de l’ordre d’élimination des super-nœuds, destiné à minimiser la longueur de la pile des matrices frontales( [AS87])
2.6.3. MLTBLC#
Cette routine construit les pointeurs du découpage en blocs de la matrice factorisée. Chaque bloc contiendra les colonnes d’un nombre entier de super-nœud. On ne rencontrera jamais la configuration où les différentes colonnes d’un même super-nœud appartiendraient à 2 blocs.
Données :
\(\mathit{MAXBLOC}\) : longueur maximum des blocs. Chaque bloc contiendra les colonnes d’un maximum de super nœuds. \(\mathit{MAXBLOC}\) est calculé avant l’appel à MLTBLC, c’est en fait la longueur (en colonnes) du plus gros des super-nœuds, et ce dernier (en général le plus haut dans l’arborescence) occupera un bloc à lui seul.
Résultats :
\(\mathit{NBLOC}\) : Nombre de blocs.
\(\mathit{LGBLOC}(\mathrm{1 }:\mathit{NBLOC})\) : longueurs de chaque bloc.
\(\mathit{NCBLOC}(\mathrm{1 }:\mathit{NBLOC})\) : définition des blocs, comme suit le bloc \(\mathit{IB}\) est constitué des colonnes des super-nœuds \(\mathit{SEQ}(\mathit{NCBLOC}(\mathit{IB}-1)+1)\) , à \(\mathit{SEQ}(\mathit{NCBLOC}(\mathit{IB}))\) .
\(\mathit{DECAL}(\mathrm{1 }:\mathit{NBSN})\) tableau de décalage qui permet d’accéder au premier terme diagonal de chaque super-nœud dans la matrice factorisée. On va illustrer cela par le schéma suivant:
ISN=0
Pour IB = 1,NBLOC ! Boucle sur les blocs de la factorisée
JEVEUO(JEXNUM(FACTOL,IB),”L”,IFACL)
! Le bloc IB de la collection FACTOL est chargé en IFACL
Pour NC = 1, NCBLOC(IB) ! Boucle sur les Super-nœuds du bloc IB
ISN = ISN +1
SN = SEQ(ISN) ! On suit la séquence d’élimination
ADFAC= IFACL + DECAL(SN) –1
! ADFAC est l’adresse dans ZR du premier coefficient du super-noeud SN
2.6.4. MLTPAS#
Cette routine calcule les adresses dans la matrice factorisée, des coefficients de la matrice initiale.
Ces adresses sont stockées dans la structure MLTF.ADNT, de nom FORTRAN \(\mathit{ADINIT}\) ou \(\mathit{COL}\) de longueur \(\mathit{LMAT}\) .
N.B. Particularité de programmation.
Certaines adresses calculées de \(\mathit{ADINIT}\) sont négatives. En effet dans le cas non-symétrique, on a 2 matrices initiales \(\mathit{MATI}\) et \(\mathit{MATS}\) qui ont la même topologie, (mêmes voisins, même creux), la factorisation symbolique est la même.
Cependant, il peut arriver qu’un coefficient de \(\mathit{MATI}\) (partie inférieure de la matrice initiale), ait une destination dans la partie supérieure de la matrice factorisée. (De façon identique entre \(\mathit{MATS}\) et la partie inférieure de la factorisée). Dans ce cas l’adresse du coefficient initial est stockée négative et la routine d’injection des coefficients de la matrice initiale, MLTASAle prend en compte et adresse correctement les coefficients .
IF( CODE.GT.0 ) THEN
ZR(IFACL+ADPROV-DEB) = ZR(MATI+I1-1): MATI injectée dans IFACL(ower)
ZR(IFACU+ADPROV-DEB) = ZR(MATS+I1-1)
ELSE
ZR(IFACL+ADPROV-DEB) = ZR(MATS+I1-1)
ZR(IFACU+ADPROV-DEB) = ZR(MATI+I1-1) MATI injectée dans IFACU(pper)
ENDIF
2.7. Arbre d’appel de MLTPRE#
|