r6.02.02 Solveur linéaire par la méthode multifrontale MULT_FRONT#

Résumé:

La méthode multifrontale MULT_FRONT est une méthode directe particulièrement adaptée à la résolution des systèmes linéaires dont la matrice est creuse. Cette méthode comprend une phase préliminaire de renumérotation destinée à minimiser le remplissage de la matrice au cours de la factorisation.

Cette phase permet aussi de regrouper les variables en « super-variables » ou « super-nœuds ». La factorisation, quant à elle, est effectuée sous la forme d’une suite d’élimination de super‑nœuds, dans des matrices pleines. Ces matrices pleines permettent l’utilisation de routines optimisées comme les BLAS, qui obtiennent les meilleures performances sur machines vectorielles ou scalaires.

Disposant de la matrice factorisée, chaque résolution de système ne nécessitera plus qu’une « descente/remontée » peu coûteuse.

Table des matières

Implantation et utilisation dans Code_Aster#

L’utilisation de la méthode multi-frontale est accessible par l’opérateur NUME_DDL, de la façon suivante:

nu = NUME_DDL (matr_rigi = matr, stockage = 'MORSE',

renum = 'MD'

ou renum= 'MDA',

ou renum= 'METIS') ;

Deux autres méthodes de renumérotation sont disponibles: Minimum Degré approché (MDA), qui est une variante de la méthode du minimum degré, et une méthode de dissection emboîtée (METIS). Elles sont décrites brièvement en annexes 1 et 2. Il suffit de remplacer la valeur de renum par MDA, ou METIS.

Cette méthode est également directement disponible sous le mot-clé SOLVEUR dans MECA_STATIQUE, STAT_NON_LINE, DYNA_NON_LINE, THER_LINEAIRE, THER_NON_LINE avec la même logique.

Ensuite, on utilisera l’opérateur FACTORISER, l’appel étant le même que dans le cas d’une matrice stockée suivant le mode profil.

Dans NUME_DDL, on indique que la matrice à factoriser est rangée suivant le mode MORSE et que l’on demande une des deux renumérotations du « minimum degree », ou une renumérotation par dissection emboîtée (METIS).

Dans ce cas, NUME_DDL effectue les trois premières phases vues précédemment:

  1. renumérotation,

  2. factorisation symbolique,

  3. séquence d’exécution.

Depuis un récent développement, la renumérotation s’effectue sur les nœuds (au sens de l’interpolation), et non plus sur les degrés de liberté. Cela permet un gain de temps de calcul et assure le respect de l’ordre initial des degrés de liberté. à l’intérieur des nœuds (cela est parfois nécessaire dans le cas incompressible où la pression doit être numérotée après les déplacements). La contrainte de numérotation des « double-lagrange » encadrant les degrés de liberté. affectés par la condition aux limites est aussi respectée.

En outre, NUME_DDL prépare le découpage par blocs de la matrice factorisée. En effet, on a vu qu’à chaque élimination, on rangeait dans un tableau les colonnes de la matrice factorisée. Ces colonnes ne serviront que lors de la descente/remontée. Elles ne servent jamais au calcul d’autres colonnes. Il n’y a donc aucun intérêt à les avoir toutes en mémoire. Elles sont rangées, dans le Code_Aster , sous la forme d’une collection d’objets JEVEUX de longueur variable. Ces objets, blocs de colonnes, doivent néanmoins satisfaire la contrainte suivante: chaque bloc correspond à un nombre entier de « supernœuds ». On ne peut donc avoir les colonnes d’un même « supernœud » sur plusieurs blocs.

Étant donné que l’on ne connaît pas la place en mémoire disponible lors de la factorisation numérique, on décide dans NUME_DDL que la longueur maximum de chaque bloc sera le max. (sur tous les SN) de la somme des longueurs des colonnes du \(\mathit{SN}\) .

\(L{b}_{\max}=\underset{\mathrm{SNi}}{\mathrm{Max}}(\sum_{k\in \mathrm{SNi}}\mathrm{longueur}({\mathrm{col.}}_{k}))\text{},\text{}\text{(en abrégé)}\)

L’opérateur FACTORISER utilise les pointeurs créés par NUME_DDL et la matrice initiale MORSE. Il crée la matrice factorisée sous la forme d’une collection d’objets JEVEUX, comme on l’a vu précédemment. Une structure de donnée provisoire est aussi nécessaire. Elle concerne les matrices frontales. Deux cas se présentent:

  • la pile des matrices frontales peut tenir toute entière en mémoire (dans un tableau monodimensionnel), dans ce cas, on alloue un objet JEVEUX et l’algorithme multifrontal gère alors lui-même cet espace, en rangeant la matrice frontale « mère » à la place des matrices « filles »,

  • elle ne tient pas et, dans ce cas, elle est créée sous la forme d’une collection d’objets JEVEUX, chaque matrice frontale étant un objet. Pour l’élimination du « supernœud » \(i\) il faut simultanément en mémoire:

  • le bloc de la factorisée auquel appartient le \(\mathrm{SNi}\)

  • l’objet matrice frontale \(i\) ainsi que toutes les matrices frontales « fille » de \(i\) qui seront détruites après leur utilisation.

La matrice frontale \(i\) sera, elle, conservée en mémoire jusqu’à son utilisation et sa destruction. On pourrait, comme il était fait auparavant, libérer au sens de JEVEUX chaque matrice frontale après sa création. Cela peut entraîner alors, en cas de faible mémoire disponible, un stockage sur disque rédhibitoire en volume. En effet, une destruction d’objet JEVEUX n’entraîne pas la destruction de son image sur disque, et la somme des longueurs des matrices frontales est énorme.

En résumé, il faut pouvoir ranger simultanément en mémoire:

  • un bloc de la factorisée,

  • la pile des matrices frontales, en un seul objet si cela tient, en plusieurs objets sinon.

Il faut donc « suffisamment » de mémoire pour utiliser la méthode multifrontale. La seconde manière de ranger la pile permet l’exécution quand la mémoire est suffisante, mais émiettée.

Quand la mémoire est insuffisante, il faut relancer l’exécution de FACTORISER avec une mémoire plus grande.

Bibliographie#

  1. I.DUFF: Parallel implementation of multifrontal scheme ». Parallel computing 3, pp.193-201 (1986)

  2. C.ROSE: Une méthode multifrontale pour la résolution directe des systèmes linéaires. Note HI-76/93/008

  3. An approximate minimum degree ordering algorithm, Tim DAVIS, Patrick AMESTOY, Iain DUFF, Technical Report TR 94-039, (SIAM J. Matrix Analysis & Applications, vol 17, no.4, (1996), pp. 886-905).

  4. The evolution of the minimum degree ordering ordering, A. George, J. Liu, SIAM review, vol 31 1989. On peut aussi consulter les sites internet suivants: http://www.cerfacs.fr - http://ww.cise.ufl.edu/~davis

  5. METIS: A software package for partitionning unstructured graphs,partitioning meshes, and computing fill oredering of sparse matrices Version 4.0. Georges Karypis &Vipin Kumar

  6. A fast and high quality MultiLevel Scheme for partitioning irregular graphs. SIAM journal on Scientific Computing 1998, Vol 20 No 1. Georges Karypis & Vipin Kumar

Description des versions du document#

Version Aster

Auteur(s) Organisme(s)

Description des modifications

5

C.ROSE-EDF/R&D/SINETICS

Texte initial

8.4

C.ROSE-EDF/R&D/SINETICS

Documentation de référence de la méthode «Approximate Minimum degree»

L’algorithme du «minimum degree» consiste a numéroter les nœuds d’un graphe dans l’ordre croissant du nombre de leurs voisin. En voici une description simplifiée mais essentielle.

  1. on forme le graphe initial associé à la matrice creuse à factoriser,

  2. on calcule le nombre des voisins des nœuds (leur degré),

  3. on numérote en premier (puis élimine du graphe), le nœud ayant le moins de voisins (degré minimum),

  4. on remet à jour le graphe de l’étape 1,

  5. on retourne à l’étape 2.

Le calcul du degré des nœuds est une opération coûteuse en temps de calcul. La méthode «Approximate Minimum degree» [bib3] se propose de réduire ce coût. Pour cela, au lieu de calculer le degré réel d’un nœud on se contente d’un majorant (souvent égal, d’après les auteurs, au vrai degré), de calcul plus facile. En effet au cours de l’élimination le vrai degré du nœud \(i\) est égal à \({d}_{i}\) , cardinal de l’ensemble suivant: \({A}_{i}\cup \lbrace {L}_{e}\rbrace\) , où l’union est faite sur l’ensemble des voisins \(e\) , précédemment éliminés, de \(i\) (termes de remplissage), et où \({A}_{i}\) est l’ensemble des voisins initiaux. Dans la méthode approchée \(i\) est remplacé par \({d}_{i}=\text{card}({A}_{i})+\sum\text{card}\lbrace {L}_{e}\rbrace\) , c’est-à-dire que l’on néglige l’intersection des \({L}_{e}\) .

Cette méthode est décrite dans [bib3] et les différentes variantes de l’algorithme du «minimum degree» sont exposées dans [bib4].

Documentation de référence METIS

L’implémentation du module de renumérotation pour matrices creuses METIS est décrit dans la note [bib5], fournie dans le répertoire METIS-4.0/Doc du logiciel. L’algorithme utilisé est décrit dans [bib6]

Il est aussi possible de consulter l’adresse internet suivante : http://www.cs.umn.edu/~karypis

METIS est principalement un outil de découpage de graphes (maillages), visant les 2 buts suivants:

  • découper un graphe donné en \(p\) sous-graphes ayant des tailles les plus proches possibles,

  • minimiser la taille des frontières entre les sous-graphes.

Le premier but vise un bon équilibre de parallélisation sur \(p\) processeurs et le second vise à minimiser les communications.

METIS utilise un algorithme de partition de graphes à plusieurs niveaux, procédant de la façon suivante: à chaque niveau on cherche des séparateurs (ensemble de cotés), de tailles minimales coupant le graphe en parties égales. METIS applique ce principe à la renumérotation des nœuds d’un graphe en cherchant à chaque étape un séparateur divisant le graphe en 2 sous-graphes. On numérote en tête les nœuds du premier sous‑graphe, ensuite ceux du second, puis ceux du séparateur. On applique ensuite le même algorithme aux 2 sous graphes de façon récursive.