1. Introduction

On décrit dans cette note l’implémentation informatique du solveur multifrontal, dans C ode_Aster . Il est destiné aux développeurs du code et n’est pas un document «autoporteur».

Cette méthode a été développée sous la forme de prototype au sein du groupe ISA en 1993 [RO93], et introduite ensuite dans Code_Aster en 1994, dans une forme adaptée à ce code:

• Factorisation d’une matrice non nécessairement en mémoire centrale («out of core»), basée sur le progiciel JEVEUX.

• Traitement des conditions aux limites avec multiplicateurs de Lagrange.

• On supposait en outre ne pas avoir besoin d’activer une recherche de pivot.

Dans un premier temps, seule une version séquentielle pour matrice réelle symétrique a été implémentée dans Code_Aster .

Par la suite les versions non-symétriques et complexes ont été introduites.

Le parallélisme complet a été développé dans le prototype [RO95], il n’a pas été retenu pour la version développée dans Code_aster. Les raisons en sont les suivantes:

• L’objectif prioritaire à l’époque était d’optimiser l’occupation en mémoire afin de traiter des systèmes linéaires de grande taille. Or le parallélisme nécessite plus de mémoire que le séquentiel.

• Le parallélisme de la multi-frontale nécessite une gestion de la mémoire parallèle propre à cette méthode, qui aurait dû cohabiter avec le progiciel JEVEUX, intrinsèquement séquentiel.

• Le parallélisme n’était pas non plus une priorité à cette époque où l’on ne disposait que de calculateurs faiblement parallèles.

On trouvera une base théorique sur la méthode dans [DU86], [AS87], [RO93] & [RO95], ainsi que dans la documentation de référence de Code_Aster : «Solveur linéaire par la méthode Multi-Frontale», [R6.02.02].

La version double précision REAL*8 (resp. COMPLEX*16) est réalisée par l’appel à la routine FORTRAN mulfr8 (resp. mlfc16).

Par la suite on décrira en détail la version pour matrice symétrique de variable réelle, des paragraphes seront consacrés aux versions non symétrique et complexe. Pour plus de détails sur les structures de données de C ode_Aster , on se référera aux documentations [D4.06.07] ( sd_ nume_ddl ) et [D4.06.10] ( sd_matr_asse ).

1.1. Principes généraux.

On veut remplacer lafactorisation d’une matrice creuse, par une suite de factorisation de matrices pleines. C’est le principe cartésien: remplacer un problème difficile par un ensemble de problèmes simples.

Pour cela on dispose d’abord d’un algorithme de renumérotation des variables du système. Cet algorithme (de degré minimum, par exemple), permet de minimiser l’ordre des matrices pleines à factoriser, c’est le premier axe d’efficacité de la méthode.

En outre, de cette renumérotation, on peut extraire les deux produits suivants:

• Un arbre d’élimination, obtenu à partir du «creux» (sparsity) de la matrice initiale et du remplissage optimum issu de la renumérotation. Ce graphe (en forme d’arborescence) fournit l’ordre d‘élimination des variables et induit le parallélisme. (En effet un nœud «fils» doit être éliminé avant un nœud «père», mais tous les «fils» d’un même «père» peuvent être éliminés indépendamment, c’est à dire en parallèle.) Ce parallélisme est le deuxième axe d’efficacité de la méthode.

• La notion de super-nœud. Cette notion a été conçue, initialement, pour minimiser le coût (non négligeable) de la renumérotation. En simplifiant, on appelle super-nœud, un ensemble de nœuds (au sens de la théorie des graphes), ayant les mêmes voisins. L’arborescence citée ci-dessus, est en fait formée de super-nœuds dont la taille augmente quand on monte dans l’arborescence, cette augmentation est une illustration du remplissage dû à la méthode d’élimination de Gauss. Ce regroupement a l’intérêt suivant: on élimine les variables par groupe, et non une par une, permettant ainsi l’utilisation de méthodes par bloc efficaces (à l’aide de BLAS de niveau 2 ou 3, produits matrice*vecteur ou matrice*matrice). Ce travail par bloc est le troisième axe d’efficacité.

En résumé, les 3 lignes de force de la méthode sont:

• Une renumérotation,

• Un arbre d’élimination,

• Un regroupement des variables.

La factorisation numérique se déroule alors comme suit:

On parcourt l’arbre d’élimination, à chaque étape (élimination du super-nœud), on dispose d’une matrice pleine associée au super-nœud et à ses voisins, on effectue l’élimination de Gauss limitée aux variables du super-nœud. On obtient ainsi d’une part les colonnes de la factorisée finale (variables du super-nœud), et une matrice frontale modifiée et réduite aux voisins («complément de Schur»), qui sera assemblée dans la matrice frontale des variables du super-nœud «père».

1.2. Programmation de la méthode.

En règle générale, la programmation de la méthode multi-frontale est divisée en 2 phases:

• une phase de factorisation dite «symbolique», incluant la renumérotation,

• une phase de factorisation numérique proprement dite.

Dans Code_Aster , la renumérotation et la première phase sont réalisées par l’appel à la subroutine MLTPRE (appelé via MLFC16 et MULFR8, dans les routines «chapeau»TLDLG2 et TLDLG3).

La deuxième phase est réalisée via l’appel à ces routines MLFC16 et MULFR8, dans les cas complexe ou réels.