RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

Minimisation
de calculs matriciels,
applications
aux éléments finis et
aux problèmes
de croisements.

Bertrand Mercier

Raymond Trémolières

Rapport de Recherche n° 3

Janvier 1973
<figure><img src="image_2.png" /></figure>
MINIMISATION DES CALCULS MATRICIELS
APPLICATIONS AUX ÉLÉMENTS FINIS
ET AUX PROBLEMES DE CROISEMENTS

B. Mercier, R. Trémolières

RESUME :

On présente dans ce travail diverses méthodes pour la recherche
d'une disposition optimale des éléments non nuls des matrices lorsqu'il
s'agit de minimiser les calculs impliqués par des opérations matri-
cielles. On montre en quoi l'on peut ainsi résoudre de façon heuris-
tique le difficile problème de la minimisation des croisements
d'arêtes reliant des points situés sur deux niveaux.

MOTS-CLEF :

Algèbre, Equations aux dérivées partielles, éléments finis,
théorie des graphes, minimisation de croisements.
<figure><img src="image_3.png" /></figure>
"Le caractère absolu qu'on reconnaît
à ce qui est simple ne concerne pas
l'être des choses mais bien la manière
dont elles peuvent être connues".

Michel FOUCAULT : Les mots et les choses.
NRF 1966.

## INTRODUCTION

Nous abordons dans cette étude un problème auquel nous avons dû faire face plusieurs fois au cours des ces dernières années. A vrai dire, ce n'était pas un mais deux problèmes essentiels qui se posaient à nous. Chronologiquement le premier problème à résoudre était de façon schématique celui de la minimisation des croisements d'arêtes reliant des points situés sur deux droites parallèles. Ce problème-classique dans sa définition- ne semblait pas avoir passionné les chercheurs mais c'est que sa simplicité apparente en masquait un très difficile de combinatoire. Pourtant sa résolution apparaît bien comme fondamentale puisqu'il s'agit finalement de résoudre des problèmes aussi divers que ceux de :

- la fiabilité maximum des cablages de plaquettes

- la présentation claire de tableaux de relations :
  tableaux hiérarchiques, sociogramme, etc...

- la reconnaissance, dans des graphes de relations, de sous-groupes d'éléments fortement liés entre eux.

Nous avons dû faire face un peu plus tard à un autre problème qui ne semblait guère -à priori- avoir de point commun avec le précédent. Il s'agissait de minimiser le nombre de calculs à effectuer lors de produits matriciels portant sur des matrices creuses (c'est-à-dire comprenant une forte densité d'éléments nuls). Nous nous aperçûmes par la suite que ce problème en recouvrait un autre qui concernait la numérotation optimale des structures en "éléments finis". Cette numérotation apparaissait en effet comme primordiale en ce qui concerne la réduction de l'encombrement en mémoire et la minimisation des calculs nécessaires à la résolution de problèmes aux dérivées partielles intervenant dans la mécanique des milieux continus.
La nécessité du moment nous fit alors nous pencher sur le pro-
blème de la réduction de"l'encombrement" des matrices et de la
numérotation optimale des structures "d'éléments finis". Et c'est
d'ailleurs cette étude qui nous permit de nous rendre compte qu'il
existait un lien étroit entre la minimisation des croisements
et la minimisation des calculs matriciels. La méthode que nous pro-
posions pour la résolution du second problème s'averait être ex-
cellente pour la résolution du premier.

Dans ce qui suit nous nous exposerons un certain nombre
de méthodes, pour la réduction des calculs dans les produits matri-
ciels, notant au passage en quoi cela peut donner un moyen efficace
et satisfaisant pour la résolution des problèmes de croisement.

Nous donnerons les résultats sur les performances des
différents algorithmes proposés.

Il convient de noter au préalable que le problème portant
sur la minimisation des calculs matriciels a déjà fait l'objet
de quelques études. Ces études sont peu nombreuses, toutes récentes,
et dans leur ensemble ne sont valable que sous la stisfaction
d'hypothèses de départ assez restrictives (cf. la Bibliographie).
Nous nous placerons ici dans le cadre de matrices quelconques, ni
forcément symétriques, ni même carrées. Il s'agit donc de méthodes
applicables à n'importe quelle matrice et dont l'efficacité devrait
présenter quelque utilité.

Le plan sera le suivant :

I - **REDUCTION DE LA ZONE EFFICACE DES MATRICES QUELCONQUES.**

1°/ - Algorithme de réduction de la zone efficace.

2/ - Algorithme des successeurs et applications.

3°/ - Algorithmes heuristiques de pénalisation de la distance
à la diagonale.

II - ALGORITHMES SPECIFIQUES POUR LES MATRICES SYMETRIQUES

1°/ - Relation avec les problèmes d'éléments finis.

2°/ - Comparaison de l'algorithme de réduction et de l'algorithme de Rosen

3°/ - Algorithme heuristique de Cuthill et Mac Kee

-Application à la Méthode Frontale-
III - RESULTATS NUMERIQUES ET COMPARAISON DE METHODES

A - Matrices rectangulaires.

B - Matrices carrées non symétriques.

C - Matrices symétriques.

+ _ + _ + _ + _ + _ + _
ORIENTATION

Etant donnée une matrice B d'éléments b$_{ij}$, i=1,...,M, j=1,...,N
nous nous proposons de trouver une disposition optimale des lignes
et des colonnes de façon à regrouper au mieux les éléments non nuls
de cette matrice. Nous allons illustrer un des intérêts de ce
problème par un exemple. Soit

$$
A = \begin{array}{c|c}
 & A B C D E F \\
\hline
a & 1 \ 1 \ 0 \ 0 \ 0 \ 0 \\
b & 0 \ 1 \ 0 \ 0 \ 0 \ 0 \\
c & 0 \ 1 \ 1 \ 0 \ 0 \ 0 \\
d & 0 \ 1 \ 1 \ 0 \ 0 \ 0 \\
e & 0 \ 0 \ 1 \ 1 \ 1 \ 0 \\
f & 0 \ 0 \ 0 \ 0 \ 1 \ 0 \\
g & 0 \ 0 \ 0 \ 0 \ 0 \ 1
\end{array}
$$

une matrice à mettre en mémoire, en vue, par exemple de la résolu-
tion d'un système Ax=f par la méthode de Gauss.

Si cependant la matrice est assez creuse il peut être utile de
repérer pour chaque ligne le premier et le dernier élément non nuls.

Supposons maintenant que la matrice A soit donnée sous une
forme A' moins "condensée", par exemple :

$$
A' = \begin{array}{c|c}
 & C A D F E B \\
\hline
a & 0 \ 1 \ 0 \ 0 \ 0 \ 1 \\
b & 0 \ 0 \ 0 \ 0 \ 0 \ 1 \\
c & 1 \ 0 \ 0 \ 0 \ 0 \ 1 \\
e & 1 \ 0 \ 1 \ 0 \ 1 \ 0 \\
d & 1 \ 0 \ 0 \ 0 \ 0 \ 1 \\
f & 0 \ 0 \ 0 \ 0 \ 1 \ 0 \\
g & 0 \ 0 \ 0 \ 1 \ 0 \ 0
\end{array}
$$

Le procédé de stockage considéré précédemment amène à réserver
39 mémoires dans le 2e cas et 26 dans le 1er cas
Il apparaît donc qu'une disposition optimale des lignes et des colonnes soit particulièrement intéressante.

Remarque :

Puisque la valeur des éléments non nuls importe peu nous ne travaillerons dans la suite qu'avec des matrices booleènnes.

On verra par la suite qu'il est beaucoup plus avantageux en mémoire et en temps, d'effectuer l'élimination de Gauss sur A que sur A'.

Ce procédé, qui est finalement sans grand intérêt lorsque l'on travaille avec des matrices de petite dimension, trouve un intérêt primordial dès que l'on a affaire à des matrices creuses de grande taille. En effet, l'écart concernant la place en mémoire et le nombre de calculs peut s'accroître de façon considérable.

Comme nous l'avons déjà dit ce problème est voisin de celui de la minimisation des croisements entre deux niveaux : on peut en effet considérer toute matrice 0-1 comme la matrice booleane d'un graphe et plus particulièrement d'un graphe bipartis (i.e. à deux niveaux). Les graphes bipartis G' et G des matrices A' et A sont en effet respectivement

<figure><img src="image_4.png" /><figcaption>Fig. 1</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 2</figcaption></figure>
Les graphes $G'$ et $G$ ont respectivement 29 et 1 croisements (¹)
et il est certain que, sans nous pencher sur les diverses appli-
cations de ce problème, le graphe $G$ est plus agréable que le graphe $G'$.

Nous devons cependant faire remarquer que le problème de la
réduction de l'encombrement des matrices et celui de la minimisation
du nombre de croisement dans un graphe ne sont pas équivalents.
Ils sont cependant suffisamment proches pour ne pas les séparer
à priori.

<footnote>(¹) Un moyen simple de calculer le nombre de croisements à partir d'une matrice de liaison A composée de 0 et de 1 est de faire la somme pour tous les éléments non nuls de A du nombre de "1" que chaque élément non nul possède dans sa partie strictement supérieure et strictement à droite.</footnote>
# I - REDUCTION DE LA ZONE EFFICACE DES MATRICES QUELCONQUES

Nous donnons dans cette partie 3 algorithmes pour la réduction
de l'encombrement des matrices.

## 1°/ - Algorithmes de réduction de la zone efficace

### Définition

On appelle vecteur dimension efficace en ligne de la matrice
A(M,N) le vecteur µ à M composantes, avec $\mu_i = 1 + j_2 - j_1$

où $j_2$ est le plus grand indice $\in [1,N]$ tel que $a_{ij_2} : 0$
$j_1$ est le plus petit indice $\in [1,N]$ tel que $a_{ij_1} : 0$

### Exemple :

$$
A = \begin{pmatrix}
1 & 0 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 1
\end{pmatrix}
\qquad
\mu = \begin{pmatrix}
5 \\
3 \\
1 \\
1 \\
3
\end{pmatrix}
$$

de la même façon on définira le vecteur dimension efficace en
colonnes $v$.

Ici, pour la matrice A : $v = (3,4,1,4,5)$ on appelle zone efficace de la matrice A la quantité

$$
e(A) = \max \left( \max_{i \in [1, M]} \mu_i, \max_{j \in [1, N]} v_j \right) \\
(ici, e(A)=5)
$$
### Problème :

Trouver une permutation des lignes et des colonnes qui minimise la zone efficace.

### exemple :

$$ 
\begin{array}{l}
\text{si } p_1 = (4,3,1,5,2) \\
p_2 = (3,1,5,2,4)
\end{array}
$$

en posant $\tilde{A} = A [p_1 ; p_2]$

(ce qui veut dire :

$$ a_{ij} = a_{p_1(i), p_2(j)} \quad i \in [1, M] \quad j \in [1, N] $$

on obtient :

$$ \tilde{A} = \begin{array}{c|ccccc} & A & E & B & D & C \\ \hline c & 1 & 0 & 0 & 0 & 0 \\ a & 1 & 1 & 0 & 0 & 0 \\ e & 0 & 1 & 1 & 1 & 0 \\ b & 0 & 0 & 1 & 1 & 0 \\ d & 0 & 0 & 0 & 0 & 1 \end{array} $$

il est aisé de voir que l'on ne peut réduire la zone efficace de A. La matrice A est la matrice _optimisée_ de A.

On notera qu'il y a en général plusieurs matrices optimisées d'une matrice A, par exemple la matrice suivante :

$$ A = \begin{array}{c|ccccc} & C & A & E & B & D \\ \hline d & 1 & 0 & 0 & 0 & 0 \\ c & 0 & 1 & 0 & 0 & 0 \\ a & 0 & 1 & 1 & 0 & 0 \\ c & 0 & 0 & 1 & 1 & 1 \\ b & 0 & 0 & 0 & 1 & 1 \end{array} $$
Autre critère de minimisation, on peut résoudre le problème en adoptant comme critère :

$$e = \sum_{i=1}^{M} u_i + \sum_{j=1}^{N} v_j$$

## Minimisation de croisements

Nous allons voir qu'il y a une relation entre les problèmes précédents et ceux qui consistent à minimiser les croisements entre deux niveaux :

On dispose sur un niveau les "numéros" des colonnes de la matrice A, sur un deuxième niveau les numéros des lignes et l'on relie les lignes-colonnes qui possèdent un élément non nul à leur intersection.

<figure><img src="image_6.png" /><figcaption>Fig. 3</figcaption></figure>

Le ré-arrangement correspondant à la matrice Ã donne

<figure><img src="image_7.png" /><figcaption>Fig. 4</figcaption></figure>
Il est aisé de constater que le croisement ((B,b), (D,e)) ne peut être supprimé. On a donc "minimisé" les croisements entre les deux niveaux.

On notera que la matrice A de 2.1 définit 8 croisements et les matrices $\tilde{A}$ et $A$ définissent 1 croisement.

### 3.3 - Algorithme

**Critère d'amélioration.** Soient A une matrice et $\tilde{A}$ une matrice issue de A par permutation des colonnes, nous dirons que $\tilde{A}$ est meilleure (en ligne) que A, ($\tilde{A} < A$) si

$$ \max_i \mu_i^A < \max_i \mu_i^A $$

ou bien, si ces deux quantités sont égales, lorsque le nombre de lignes où le "max" est atteint décroît strictement.

**Par exemple avec :**

$$ \text{1.1) } A = \begin{array}{c} a \\ b \\ c \\ d \\ e \end{array} \begin{array}{c|c} A & B & C & D & E \\ \hline 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \end{array} \quad \tilde{A} = \quad \begin{array}{c} a \\ b \\ c \\ d \\ e \end{array} \begin{array}{c|c} B & A & C & D & E \\ \hline 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \end{array} \quad A = \quad \begin{array}{c} a \\ b \\ c \\ d \\ e \end{array} \begin{array}{c|c} B & C & A & D & E \\ \hline 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \end{array} $$

On a :

$$ \max_i \mu_i^A = \max \begin{subarray}{c} 5,2,2,3,5 \\ i \end{subarray} = 5, $$

$$ \max_i \mu_i^A (\tilde{A}) = \max \begin{subarray}{c} 4,3,2,4,4 \\ i \end{subarray} = 4, $$

$$ \max_i \mu_i^A (\tilde{A}) = \max \begin{subarray}{c} 3,2,3,4,4 \\ i \end{subarray} = 4, $$

d'où :

$\tilde{A}$ est meilleure que $A$, meilleure que $A$.
## Algorithme

D'une façon générale, on améliorera en ligne (resp. en colonne) la matrice A, par des permutations successives sur les numéros des colonnes (resp. des lignes).

En pratique, on essayera des transpositions.

Le calcul de la dimension efficace en ligne coûtant relativement cher, il importe de sélectionner le plus vite possible une transposition améliorante. On essaye donc d'abord les transpositions qui échangent un zéro encadré par des "1" dans une ligne, avec 1'un ou 1'autre des "1" qui l'encadrent. Lorsqu'aucune transposition n'améliore plus A ni en ligne, ni en colonne, l'algorithme a convergé.

On peut également essayer des "glissements". Nous appelons glissement $(i,j)$ la transformation sur $[1,...,N]$ qui met l'élément $i$ à la jème place, et qui décale tous les éléments de l'intervalle $[i,j] \subset [1,N]$ d'un cran vers $i$.

exemple : $N=8$

$G_{2\ 5}$ est la permutation $1,3,4,5,2,6,7,8$

$G_{6\ 3}$ est la permutation $1,2,6,3,4,5,7,8$.

Nous allons illustrer ce processus sur un exemple.

Exemple de réduction de la zone efficace d'une matrice A.

Soit

<table><thead><tr><th></th><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>μ (A)</th></tr></thead><tbody><tr><th>a</th><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>5</td></tr><tr><th>b</th><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>2</td></tr><tr><th>c</th><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>2</td></tr><tr><th>d</th><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>3</td></tr><tr><th>e</th><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>5</td></tr></tbody></table>
Nous allons d'abord réduire la dimension efficace en ligne. (Nous indiquons à droite des matrices la dimension efficace des vecteurs lignes). L'Algorithme 1 donne successivement, en cherchant à positionner le "0" d'abord vers la gauche :

$$A = \begin{array}{c|ccccc}
 & B & A & C & D & E \\
\hline
a & 0 & 1 & 0 & 0 & 1 \\
b & 1 & 0 & 1 & 0 & 0 \\
c & 1 & 1 & 0 & 0 & 0 \\
d & 1 & 0 & 0 & 1 & 0 \\
e & 0 & 1 & 1 & 0 & 1
\end{array} \qquad \begin{array}{c} \mu(A) \\ 4 \\ 3 \\ 2 \\ 4 \\ 4 \end{array}$$

$$A = \begin{array}{c|ccccc}
 & B & C & A & D & E \\
\hline
a & 0 & 0 & 1 & 0 & 1 \\
b & 1 & 1 & 0 & 0 & 0 \\
c & 1 & 0 & 1 & 0 & 0 \\
d & 1 & 0 & 0 & 1 & 0 \\
e & 0 & 1 & 1 & 0 & 1
\end{array} \qquad \begin{array}{c} \mu(A) \\ 3 \\ 2 \\ 3 \\ 4 \\ 4 \end{array}$$

$$A = \begin{array}{c|ccccc}
 & D & B & C & A & E \\
\hline
a & 0 & 0 & 0 & 1 & 1 \\
b & 0 & 1 & 1 & 0 & 0 \\
c & 0 & 1 & 0 & 1 & 0 \\
d & 1 & 1 & 0 & 0 & 0 \\
e & 0 & 0 & 1 & 1 & 1
\end{array} \qquad \begin{array}{c} \mu(A) \\ 2 \\ 2 \\ 3 \\ 2 \\ 3 \end{array}$$

$$\mu(A^j) = 1,3,4,5,5$$

Cette dernière matrice étant irréductible nous cherchons maintenant à réduire la dimension efficace en colonne. On obtient :
$$A = \begin{array}{c|c} & D B C A E \\ \hline a & 0 \ 0 \ 0 \ 1 \ 1 \\ c & 0 \ 1 \ 0 \ 1 \ 0 \\ d & 1 \ 1 \ 0 \ 0 \ 0 \\ e & 0 \ 0 \ 1 \ 1 \ 1 \\ b & 0 \ 1 \ 1 \ 0 \ 0 \end{array}$$

$$v(A) = 1,4,2,4,4.$$

$$A = \begin{array}{c|c} & D B C A E \\ \hline a & 0 \ 0 \ 0 \ 1 \ 1 \\ e & 0 \ 0 \ 1 \ 1 \ 1 \\ c & 0 \ 1 \ 0 \ 1 \ 0 \\ d & 1 \ 1 \ 0 \ 0 \ 0 \\ b & 0 \ 1 \ 1 \ 0 \ 0 \end{array}$$

$$v(A) = 1,3,4,3,2.$$

$$A = \begin{array}{c|c} & D B C A E \\ \hline a & 0 \ 0 \ 0 \ 1 \ 1 \\ e & 0 \ 0 \ 1 \ 1 \ 1 \\ c & 0 \ 1 \ 0 \ 1 \ 0 \\ b & 0 \ 1 \ 1 \ 0 \ 0 \\ d & 1 \ 1 \ 0 \ 0 \ 0 \end{array}$$

$$v(A) = 1,3,3,3,2.$$

Cette dernière matrice étant irréductible le processus prend fin.

En inversant l'ordre des colonnes on obtient la disposition :

$$A = \begin{array}{c|c} & E A C B D \\ \hline a & 1 \ 1 \ 0 \ 0 \ 0 \\ e & 1 \ 1 \ 1 \ 0 \ 0 \\ c & 0 \ 1 \ 0 \ 1 \ 0 \\ b & 0 \ 0 \ 1 \ 1 \ 0 \\ d & 0 \ 0 \ 0 \ 1 \ 1 \end{array}$$
Dans ce qui précède les essais successifs ont été effectués à partir de la gauche pour la réduction en ligne, et à partir du haut pour la réduction en colonnes. En fait nous aurions pu aussi bien commencer les essais à partir de la droite et à partir du bas.

Si l'on a en vue la minimisation des croisements on pourra conduire le procédé de façon à reporter le maximum de "0" dans la partie supérieure droite et dans la partie inférieure gauche de la matrice.

**Cas des matrices symétriques : conservation de la symétrie.**

Afin de conserver la symétrie d'une matrice tout déplacement d'une colonne i devra être immédiatement suivi du même déplacement de la ligne i. L'étape de la réduction de la dimension efficace en colonne qui suit celle de la réduction de la dimension efficace en ligne n'a alors plus de raison d'être.

## 2° / - Algorithme heuristique des successeurs

### Définition :

On considère un graphe bipartis G et sa matrice booleanne A. Etant donné un noeud i d'un des niveaux, on appellera **successeur** de i tout noeud j de l'autre niveau en relation avec lui.

Par exemple si i est un niveau inférieur, les successeurs seront tous les j tels que $G_{ij} \neq 0$.

On appellera **degré** d'un noeud le nombre de ses successeurs.

L'idée de l'algorithme vient du cas particulier où le graphe se réduit à un seul chemin zigzagant entre les deux niveaux. Si on appelle a une de ses extrémités, A son successeur, b le successeur de A, et ainsi de suite : B,C,C... alors le chemin est "déroulé"

<figure><img src="image_8.png" /></figure>

réordonné
donne :

<figure><img src="image_9.png" /></figure>
## Description de l'algorithme

Partant du cas particulier agréable précédent, dans le cas général on procédera de la façon suivante :

1) trouver le noeud qui a le moins de successeurs (de degré minimal), lui donner dans son niveau le 1er numéro disponible (1 la première fois),

2) chercher les successeurs du noeud précédent, et s'ils ne sont pas déjà numérotés dans l'autre niveau, leur donner les premiers numéros disponibles.

Si l'ensemble des successeurs est vide, retourner en 1) (et si 1) est inaplicable c'est que l'algorithme est fini).

3) pour chacun des noeuds ainsi numérotés au 2), faire comme au 2).

L'algorithme est illustré par la figure suivante :
<figure><img src="image_10.png" /></figure>

ici la "chaîne" des successeurs se casse. On pioche dans la sous-matrice qui reste une autre chaîne, etc....

dernière étape

<figure><img src="image_11.png" /><figcaption>Fig. 7 : Application de l'algorithme 4 des successeurs à l'exemple de la Fig. 3.</figcaption></figure>
Lorsqu'un noeud a plus de deux successeurs, se pose le problème de savoir dans quel ordre numéroter tous ces successeurs. On peut les numéroter dans l'ordre où on les trouve, ou mieux par ordre de degré croissant.

En fait cet algorithme est heuristique. En effet, le point de départ optimal n'est pas forcément le noeud de degré minimal. Et l'ordre de numérotation des successeurs d'un même noeud peut n'avoir aucun rapport avec l'ordre des degrés, dans la solution optimale.

Mais l'expérience montre que l'algorithme ainsi conçu, donne très rapidement une solution acceptable, qui peut constituer un bon point de départ pour les algorithmes précédents.

En fait, cet algorithme résout le problème rigoureusement dans certains cas particuliers : chaînes simples, cycles simples.

Lorsqu'il n'y a pas de cycles, le problème est soluble exactement par l'algorithme suivant.

## Algorithme de répartition des poids

On considère ici un graphe biparti sans cycles (il n'existe pas de suite d'arêtes adjacentes, $u_1, u_2, \dots, u_k$, telle qu'une arête puisse être répétée 2 fois). (cf. Fig. 8).

<figure><img src="image_12.png" /><figcaption>Fig. 8 : 51 croisements.</figcaption></figure>

On peut adopter la règle de réduction du nombre de croisements qui suit.

S'il n'y a pas de sommet d'où partent 3 arêtes, on trace sans difficulté la suite des sommets sans intersection aucune. Sinon pour tout sommet d'où partent au moins 3 arêtes on opère comme
suit (soit x un tel sommet) :

- déterminer le "poids" de chacune des arêtes $u_1, u_2, u_3, \dots$
qui partent de x avec :

poids d'une arête $u_i$ (vue de x) = nombre d'arêtes du graphe qui sont reliées à x par une chaîne passant par $u_i$.

- affecter chacune de ces arêtes de son poids,

- déterminer les 2 arêtes de plus grand poids, les faire partir de chaque côté de x.

- déterminer les 2 arêtes suivantes de plus grand poids : les faire partir de chaque côté de x, mais dans l'angle des deux précédentes.

- recommencer autant que nécessaire en tracant les nouvelles arêtes dans le dernier angle aigu formé.

- On trace alors le graphe en respectant les ordres trouvés :

Ex :
<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

rien à changer

<figure><img src="image_16.png" /></figure>

rien à changer

<figure><img src="image_17.png" /></figure>

rien à changer

<figure><img src="image_18.png" /><figcaption>Fig. 9</figcaption></figure>
Graphe terminal

<figure><img src="image_19.png" /><figcaption>Fig. 10 : 20 croisements au lieu de 51.</figcaption></figure>

Dans cette configuration nous venons de placer les chaînes en tassant les plus courtes autour d'un noeud multiple. Ce procédé correspond au critère $\bar{e}$ défini dans $I-1°$.

Une autre manière de procéder serait, tout en respectant la disposition correspondante aux poids des arêtes, d'imbriquer les unes dans les autres les chaînes partant d'un même côté. On satisfait ainsi le critère $e$ de $I-1°$.

### 3°/ - Algorithmes heuristiques de pénalisation de la distance à la diagonale.

Cet algorithme consiste à permuter successivement lignes et colonnes d'une matrice quelconque A suivant une règle que nous allons préciser.

La matrice A sera supposée comporter au moins un élément non nul dans chaque ligne et chaque colonne. Comme nous ne nous intéressons qu'au "profil" de la matrice, on supposera que les éléments non nuls de A sont des 1.

Posant $A^{(0)}=A$ et supposant déterminé $A^{(n-1)}$ par l'itération $n-1$ (au départ $n=1$) on détermine $A^{(n)}$ à l'itération $n$ comme suit.

a) - Itération $n$ (cas où $n$ est impair, $=1$ au départ).

On forme une matrice $C=((c_{ij}))$ déduite de $A^{(n-1)}$ par

$$c_{ij} = jxa_{ij}^{(n-1)} \text{ avec } A^{(n-1)} = ((a_{ij}^{(n-1)})).$$

Puis on définit un vecteur $v=(v_i)_{i=1,...,M}$ par

$$v_i = \frac{\sum_j c_{ij}}{\sum_j a_{ij}^{(n-1)}}.$$
On note $m_1$ l'indice de la composante de $v$ qui a la plus
petite valeur, $m_2$ l'indice de celle qui vient après,...$m_M$ l'indice
de la plus grande.

On définit alors $A^{(n)}$ par permutation des **lignes** de $A^{(n-1)}$ selon l'ordre indiqué par le vecteur $v$, soit :

$$
A^{(n)} = \left( \left\| \begin{pmatrix} a & (n-1) \\ m_{ij} \end{pmatrix} \right\| \right)
$$

On passe alors à l'itération suivante au point b).

b) - *Itération n+1* (cas où n est impair).

On forme une matrice $D=((d_{ij})$ déduite de $A_n$ par

$$
d_{ij} = \text{ixa}_{ij}^{(n)} \quad \text{avec} \quad A^n = ((a_{ij}^{(n)})).
$$

Puis on définit un vecteur $w=(w_j)_{j=1,...,N}$ par

$$
w_j = \frac{\sum_i d_{ij}}{\sum_i a_{ij}^{(n)}}
$$

On note $n_1$ l'indice de la composante de $w$ qui a la plus petite valeur $n_2$ , l'indice de celle qui vient après,... $n_N$ l'indice de la plus grande.

On définit alors $A^{(n+1)}$ par permutation des **colonnes** de $A^{(n)}$
selon l'ordre donné par $w$, soit :

$$
A^{(n+1)} = ((a_{inj}^{(n)}))
$$

On pose alors $n:=n+2$ et l'on reprend à a).

c) - *Critère d'arrêt.*

Comme il s'agit ici d'un algorithme heuristique le critère
d'arrêt est d'un choix délicat.
Un premier procédé est de calculer à chaque permutation le nombre de "croisements" (cf. note en bas de page qui précède) et d'arrêter l'algorithme dès que ce nombre augmente au lieu de diminuer.

Un autre procédé, moins coûteux mais peut être moins sûr aussi est d'arrêter l'algorithme dès que $A_{n+2}=A_n$. En effet dans cette situation le procédé boucle. Empiriquement on arrive à cette situation dans la plupart des cas, du moins si l'on prend la précaution, lorsque $v_{h_1}=v_{h_2}$, $h_1 < h_2$ de choisir $m_k=h_1$ et $m_{k+1}=h_2$ pour k convenable, autrement dit, chaque fois qu'il y a litige dans le choix de la permutation à faire, on prend celle qui respecte l'ordre d'une précédente si elle existe.

Nous illustrons cet algorithme par un exemple.

Exemple :

$$A_o = \begin{array}{c|c} & 1234 \\ \hline & 10101 \\ & 1001 \\ & 1010 \\ & 1000 \end{array}$$

$$C = \begin{bmatrix} 0 & 2 & 0 & 4 \\ 1 & 0 & 0 & 4 \\ 1 & 0 & 3 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}$$

$$v = \begin{bmatrix} 3 \\ 2,5 \\ 2 \\ 1 \end{bmatrix} \quad \begin{array}{l} m_1=4 \\ m_2=3 \\ m_3=2 \\ m_4=1 \end{array}$$

$$A_l = \begin{array}{c|c} & 1234 \\ \hline & 41000 \\ & 1010 \\ & 1001 \\ & 0101 \end{array}$$

$$D = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 0 & 2 & 0 \\ 3 & 0 & 0 & 3 \\ 0 & 4 & 0 & 4 \end{bmatrix}$$

$$w = \begin{bmatrix} 2 & 4 & 2 & 3,5 \end{bmatrix}, n_1=1, n_2=3, n_3=4, n_4=2$$

$$A_2 = \begin{array}{c|c} & 1342 \\ \hline & 41000 \\ & 31100 \\ & 21010 \\ & 10011 \end{array}$$

$$C = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 \\ 1 & 0 & 3 & 0 \\ 0 & 0 & 3 & 4 \end{bmatrix}$$

$$v = \begin{bmatrix} 1 \\ 1,5 \\ 2 \\ 3,5 \end{bmatrix} \quad \begin{array}{l} m_1=1 \\ m_2=2 \\ m_3=3 \\ m_4=4 \end{array}$$

pas de changement de lignes à l'itération 2
$$
A_3 = \begin{bmatrix}
4 & 1 & 0 & 0 & 2 \\
3 & 1 & 1 & 0 & 0 \\
2 & 1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 1
\end{bmatrix}
$$

$D=$

$$
\begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
2 & 2 & 0 & 0 & 0 \\
3 & 0 & 3 & 0 & 0 \\
0 & 0 & 4 & 4 & 0
\end{bmatrix}
$$

$$
w = \begin{bmatrix} 2 & 2 & 3,5 & 4 \end{bmatrix}
$$

pas de changement de colonnes à l'itération 3.

On arrête ici l'algorithme puisque la matrice $A_3$ restera identique à elle-même.

Remarque 3.1 : cas des matrices symétriques.

Pour respecter la symétrie de la matrice, à chaque fois
que l'on effectue une permutation sur les lignes, on effectuera une
permutation identique sur les colonnes.

L'itération n+1 (cas où n est impair) consiste donc
uniquement à effectuer une permutation des colonnes dans l'ordre
déterminé à l'itération n.

On pourra ainsi supprimer les itérations n+1 (n impair)
en posant :

$$
A^{(n)} = ((a_{m_i, m_j}^{(n-1)})).
$$

Remarque 3.2 : On retrouve l'idée de cet algorithme dans GEORGE [6]
mais se limitant à une itération, dans le cas
symétrique, et dans DEUTSCH [4] pour des matrices
à valeurs quelconques.

Remarque 3.3 : Algorithme heuristique dérivé : pénalisation par le nombre de zéros.
Cet algorithme opère de façon identique au précédent mais
avec des matrices C et D différentes :

a) - Itération n (cas où n est impair, =1 au départ)

$$
C_{ij} = j \cdot a_{ij}^{(n=1)} + \sum_{k=i}^{j} (1 - a_{ik}^{(n-1)})
$$

b) - Itération n+1 (cas où n est impair)

$$
d_{ij} = i \cdot a_{ij}^{n} + \sum_{k=j}^{i} (1 - a_{kj}^{(n)}).
$$

Dans le cas des matrices symétriques on adaptera l'algorithme
comme indiqué à la Remarque 3.1.
## II - ALGORITHMES SPECIFIQUES POUR LES MATRICES SYMETRIQUES.

### 1°/ - Relation_avec_les_problèmes_d'éléments_finis

a) formulation d'un problème d'éléments finis.

On considère l'approximation un problème aux limites sur un ouvert $\Omega$ par des éléments finis linéaires sur des triangles.

Pour fixer les idées envisageons le problème de Neumann : on cherche $u \in V=H^1(\Omega)$ tel que :

$$ \int_{\Omega} \operatorname{grad} u \cdot \operatorname{grad} v \, dX + \int_{\Omega} uv \, dX = \int_{\Omega} gvd\Gamma \quad \forall v \in V. \quad (1) $$

On définit une triangulation $\mathcal{T}_h$ de $\Omega$ et on cherche à résoudre le problème sur cette structure.

On introduit les valeurs $u_1, \dots, u_N$ (resp. $v_1, \dots, v_N$) de n (resp. v) aux N noeuds de la triangulation.

On supposera que le triangle T a pour sommets les noeuds $(m_T(i))_{i=1,2,3}$, (cf. Figure 13).

Le problème approché s'écrira sous la forme :

$$ \begin{array}{lll} \text{t}_v \ Au = \text{t}_{vF} & \forall v \in \mathbb{R}^N & \text{où} \\ & A = ((A_{k1})) & h=1, \dots, N \\ & & l=1, \dots, N \\ & F = (F_k) & h=1, \dots, N \\ & u = (u_l) & l=1, \dots, N \end{array} $$

équivalent à résoudre un système linéaire : $Au=F$ (3)

La matrice A est telle que si aucun triangle ne contient à la fois les sommets k et l, $A_{kl}=0$ donc $A_{k1}\ne0 \Leftrightarrow k$ et l sont voisins
b) Relation avec la réduction du profil des matrices

La résolution du système linéaire (3) où A est symétrique et définie positive, peut être faite de façon efficace par la méthode de Choleski.

La première partie de cette méthode consiste à factoriser
A sous forme d'un produit $L^tL$ où L est triangulaire inférieure et
L sa transposée. En fait, au cours de la factorisation, on trans-
forme au fur et à mesure la matrice A. Mais au cours de la factori-
sation, dans chaque ligne la partie comprise entre l'élément non
nul le plus à gauche et la diagonale se remplit d'éléments non
nuls:

Exemple :

<figure><img src="image_20.png" /><figcaption>Factorisée de Choleski L</figcaption></figure>

<figure><img src="image_21.png" /></figure>

Après la factorisation on résout les systèmes :

$$
\begin{align*}
\text{Ly} &= \mathbf{F} \\
\text{et } \mathbf{t}^{\text{Lx}} &= \mathbf{y}
\end{align*}
$$

et le temps de résolution dépend très fortement du nombre
d'éléments non nuls.

L'idée est donc de renuméroter les noeuds de la triangu-
lation, et donc de faire sur A une permutation des lignes, et la
même sur les colonnes, de telle façon que tous les éléments de A
se tassent près de la diagonale.
Si nous posons $\delta_i^j = \sup_{i=1,...,N} \delta_{ij}^j$ et $\delta_{ij} = \sup_{j>i} \delta_{ij}$, nous appellerons vecteur-bande en ligne $\neq 0$ et en colonne serait $\neq 0$.

Nous appellerons **bande de la matrice A** la quantité

$$B = \sup_{i \in [I, N]^i} \delta_i$$

On appellera **profil efficace** de la matrice A la quantité $C = \sum_{i=1}^{N} \delta_i$ qui n'est autre que le nombre d'éléments non nuls dans la factorisée de Choleski.

Pour optimiser la place mémoire il faut donc minimiser C, ce qui n'est pas équivalent à minimiser B, quoique les deux problèmes soient évidemment très liés.

Pour optimiser le temps de calcul, il sera évidemment beaucoup plus facile d'avoir optimisé B, car l'accès aux éléments non nuls sera beaucoup plus rationnel (et donc plus rapide).

## 2° / - Comparaison de l'algorithme de réduction et de l'Algorithme de Rosen.

Remarquons que l'algorithme de réduction décrit au § I-1°/cherche à améliorer le vecteur dimension efficace en ligne $(\mu_i)$ (son sup ou sa somme), ce qui dans le cas d'une matrice symétrie revient à tenir compte du "vecteur-bande" en ligne $(\delta_i)$ et du "vecteur-bande en colonne. On a la relation $\mu_i = \delta_i + \epsilon_i - 1$ ($i=1,...,N$)

ROSEN [8] a conçu un algorithme dont le principe est le suivant : on améliore la bande B par étapes successives. On détermine tout d'abord un élément $a_{ij} \neq 0$ (j<i) tel que $i-j+1=B$ on dira que l'élément $a_{ij}$ "provoque la bande". On cherche alors à échanger le noeud i avec un noeud de numéro inférieur et on regarde si celà permet d'améliorer la bande de la matrice A. Si oui, on fait l'échange, si non on cherche à échanger j avec un noeud de numéro supérieur : si celà améliore la bande, on fait l'échange. Sinon on cherche à faire les mêmes opérations avec i et j même si çà n'améliore pas la bande strictement. Et si on ne peut rien faire c'est que l'algorithme a convergé.
On voit que cet algorithme est très comparable au principe
à l'algorithme de réduction.

Dans les deux cas il y a un grand nombre de fois à calculer
soit la dimension efficace en ligne, soit le vecteur-bande en ligne.
Bien que ce ne soit pas spécifié dans ROSEN [8] nous avons adopté
des critères "stricts" d'amélioration du vecteur $\delta_i$

1er critère : diminuer strictement sup $\delta_i$ ou sinon le nombre d'éléments de $\delta_i$ qui atteignent ce sup

2è critère : diminuer strictement $\sum \delta_i$.

Car si l'on n'adopte pas de critère strict, l'algorithme
finit toujours par boucler. En fait la différence essentielle
entre les deux algorithmes réside dans de choix du critère.

Introduisons une "convexité" sur les critères.

Définition 1

Etant donnée l'ensemble $\mathcal{S}$ des permutations de l'ensemble
$\{1, \dots, N\}$, et une fonction $f$ de $\mathcal{S} \to N$ ensemble des entiers
naturels.

On dira que $f$ est "quasi-convexe" pour la transposition si
$\forall p,q \in \mathcal{S} f(p) < f(q)$, il existe $p_1, p_2, \dots, p_k \in \mathcal{S}$, avec $p_1 = p$ et $p_k = q$
telles que pour $i=2, \dots, k$

$p_i$ soit déduisible de $p_{i-1}$ par une transposition
(de deux éléments).

• $f(p_i) < f(p_{i-1})$ (si on met $\leq$ : on aura la "quasi-convexité" au sens large).

Définition 2

On introduit $f: \mathcal{S} \to N$ comme plus haut une permutation $p \in \mathcal{S}$,
on dira que $f$ possède un "minimum local" si $\forall q \in \mathcal{S}$ telle que l'on
puisse passer de $p$ à $q$ par une transposition

$f(q) > f(p)$
La fonction f possèdera un "minimum global" en $\mathcal{P}$ si $\forall q \in \mathcal{P}$
$f(q) \ge f(p)$ sans aucune spécification sur q.

Si la fonction f est "quasi convexe", tout "minimum local"
sera en fait "global".

L'intérêt de cette notion réside dans le fait qu'il y a
transpositions, alors qu'il y a N! permutations.
$\frac{N(N-1)}{2}$

Il n'est pas possible avec les machines actuelles de vérifier
qu'un minimum est global à partir de N convenable. Alors qu'il
est encore possible de vérifier qu'il est local. Explicitons quelques-
uns des critères que nous avons rencontrés.

On suppose donnée une matrice A symétrique (N,N), on considère
p ∈ 𝒰 et on détermine pour A [p;p] (matrice obtenue en réordonant les
lignes et les colonnes de A suivant p dans cette matrice l'élément
(i,j) est l'élément (p(i),p(j)) de A-notation APL).

Soit $\mu(p)$ le vecteur dimension efficace en ligne de $A[p;p]$
$\delta(p)$ son "vecteur-bande" en ligne
$m(p)$ son nombre des croisements.

Critère_1 $f_1(p) = \text{Nxsup}_i \mu_i + \text{nb de lignes où sup est atteint}$
(sup dimensions efficaces).

Critère 2 $f_2(p) = \sum_i \mu_i$ (somme des dimensions efficaces).

Critère 3 $f_3(p) = \text{Nxsup}_i \delta_i + \text{nb de lignes où le sup est atteint (sup du "vecteur-bande en ligne").}$

Critère 4 $f_4(p) = \sum_i \delta_i$ (nombre d'éléments non nuls dans la factorisée de Choleski).

Critère 5 $f_5(p) = m(p)$ (nombre de croisements).

Aucun de ces cinq critères n'est "quasi-convexe". Mais ils
le sont "plus ou moins". Un critère est intuitivement "meilleur" qu'un
autre s'il a moins d'optima locaux éloignés de l'optimum global.

Le problème de trouver des critères "quasi-convexes" pour la
transposition est, à notre connaissance, ouvert. Nous avons comparé
ces critères $f_1$ et $f_3$ d'une part, et $f_2$ et $f_4$ d'autre part.
CUTHILL [3] montre un exemple d'optimum local pour le critère $f_1$ non global : on considère la matrice correspondant au graphe :

<figure><img src="image_22.png" /><figcaption>Fig. 11</figcaption></figure>

$(a_{ij}=a_{ji}=1 \text{ si } i \text{ et } j \text{ sont connectés sur le graphe}).$

Considérons la numérotation suivante :

<figure><img src="image_23.png" /><figcaption>Fig. 12</figcaption></figure>

$$f_3(p_2)=57 \text{ , donc } f_3(p_2) < f_3(p_1)$$

$p_i=1,...,N \quad (\text{la matrice est explicitée plus loin dans III-C-1°/})$

$$f_3(p_i)=68 \quad (\text{bande=5})$$

$p_2=1,4,7,10,2,5,8,11,3,6,9,12$ la bande est ici de 4.

or on voit aisément que si dans la première figure on transpose deux éléments quelconques la bande passe de 5 à 6 donc que $p_1$ est un "optimum local" pour $f_3$.

En fait il ne l'est pas pour $f_1$.

Nos résultats montrent que $f_1$ et $f_2$ sont de "meilleurs" critères que $f_3$ et $f_4$.

Mais à ce niveau seuls les résultats expérimentaux peuvent donner une indication.

De toutes façons les algorithmes travaillant par transpositions successives sont lents. Il faut donc essayer de faire un choix admissible de transposition le plus vite possible, car chaque calcul de la dimension efficace en ligne ou de la bande coûte cher.

Ces algorithmes ont l'avantage de trouver un optimum local relativement à chacun.
Remarque :

Il y a $\frac{N(N-1)}{2}$ transpositions possibles sur N objets.

Appelons glissement "G<sub>ij</sub>" la permutation de (1,...,N) telle
que

$$
G_{ij}(j)=i
$$

$$
G_{ij}(k)=k+1 \text{ pour } k=i,i+1,\dots,j-1 \text{ (si } i<j)
$$

$$
k=i, i-1, \dots, j+1 \quad (\text{si } i<j)
$$

il y en a N(N-1).

Pour les"glissements" on peut définir également une "quasi-
convexité" d'un critère, etc...

Nous avons également fait des essais avec les glissements.
(En fait un glissement est une permutation circulaire sur [i,j] ⊂ [1,N].

On peut également définir la quasi-convexité pour d'autres
opérateurs de passage simple.

3°/ - Algorithme heuristique de Cuthill et Mc Kee.

-Application à la méthode frontale-

En fait cet algorithme conçu par Cuthill et Mc Kee[3], et repris
par ARANY et MYTH [1], est une restriction au cas symétrique de
l'algorithme décrit au I 2°/.

a) <u>origine de la méthode</u>

Lorsque A est une matrice d'éléments finis, permuter les
lignes et les colonnes de A revient à rénuméroter les noeuds de la
triangulation. Finalement pour que la matrice soit la plus "bande"
possible, il faut qu'un noeud i, soit voisin de noeuds qui ont
un numéro pas trop différent de lui, que les noeuds soient "bien
numérotés" par couches successives. Le cas catastrophique étant
celui où le noeud 1 et le noeud N sont voisins, et où la bande est
alors maximale, car l'élément $a_{iN}$ est alors non nul et est à une
distance N de la diagonale).

D'où l'idée de partir d'un noeud du maillage, de lui donner le
numéro 1, de donner les numéros 2,...,n<sub>1</sub>+1 à ses n<sub>1</sub> voisins, et ainsi
de suite.
Par récurrence : on a un ensemble I de noeuds déjà numérotés.

On détermine l'ensemble J de leurs voisins ($J = \{I\}$) puis on donne les numéros $|I|+1, |I|+2, \dots, |J|$ aux éléments de l'ensemble $J-I$, on pose $I:=J$ et ainsi de suite jusqu'à ce que $I$ soit l'ensemble total.

On sent que le choix initial de $I$ : le choix du 1er élément sera très important. Si on n'a pas de renseignements, un choix pas trop catastrophique sera de partir du noeud qui a le moins de voisins possibles (Cf. Figure 13).

Lorsqu'on a le dessin d'une triangulation il est très facile de voir ce voir ce que donne cet algorithme.
<figure><img src="image_24.png" /><figcaption>Fig. 13</figcaption></figure>

Pour le triangle $T_1$ : on a
$m_T^{1}(1) = 124$
$m_T^{1}(2) = 140$
$m_T^{1}(3) = 141$
Dans ce procédé on numérote les noeuds par couches successeives, $|J-I|$ étant le nombre de noeuds dans une couche. On appelle ce nombre le "front" de la triangulation. Il est caractéristique de la topologie du domaine.

On sent que le choix du point de départ est très important : si on était parti du centre du cercle : le front maximum aurait été de 48 (soit environ $\approx 4$ fois plus grand).

Il y a lieu étroit entre le "front" et la bande de la matrice : si à l'intérieur de chaque couche les noeuds ont un numéro quelconque, la bande sera au pire 2 fois le front maximum, et au mieux le front maximum lui-même.

## b) réalisation pratique de l'algorithme

De façon pratique, on ne suppose connu que les $m_T(i)$ pour $i=1,2,3$, $T \in \mathcal{T}_h$ (cf. § II 1°/) on déduit très facilement le profil de la matrice A d'éléments finis en initialisant A à 0 et en faisant une boucle sur l'ensemble des triangles. Pour chaque triangle T on fait :

$$a_{m_T(i)} = 1 \text{ pour } i,j \in \{1,2,3\}$$

On cherche le noeud de départ qui correspond à la ligne la plus "creuse" de la matrice.

Si $I_\alpha$ est l'ancien numéro du $\alpha$ ème noeud dans la nouvelle numérotation et si l'on note $I=(I_\alpha)_{\alpha=1,...,|I|}$

On en déduit $J=\{J_\beta \mid \exists \alpha \text{ tq } a_{I_\alpha J_\beta} \neq 0\}$ et ainsi de suite.

On remarque que la matrice A n'est jamais changée, qu'on a tout de suite la nouvelle numérotation. D'autre part, on n'aura pas besoin de calculer la dimension efficace en ligne.

Cet algorithme est évidemment heuristique. Pour des comparaisons avec ROSEN [8], cf. CUTHILL [7].

## c) application à la méthode frontale

Notons tout de suite le lien qu'il y a avec la "méthode frontale" (B.M. IRONS [5]). Au lieu de former la matrice A définissant le voisinage des noeuds, on forme la matrice B qui définit celui des triangles :
$b_{T_1 T_2} = 1$ n $T_1$ et $T_2$ sont voisins
$= 0$ sinon,

l'algorithme précédent appliqué à B donne un ordre de parcours des
triangles, efficace pour l'utilisation de la "méthode frontale".
Cette méthode est en fait une élimination de Gauss qui consiste à
parcourir l'ensemble des triangles de telle façon que lorsqu'un
noeud a été atteint une première fois, il soit atteint pour la
dernière fois **le plus rapidement possible**. Ce qui permet d'''éliminer''
d'autant plus vite cette ligne, et de stocker le résultat de
l'élimination.
Si nous appliquons l'algorithme 3 nous obtenons la matrice :

```
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0
1 0 1 0 0 1 0 0 0 0
0 1 0 0 0 0 1 0 0 0
0 1 0 0 1 0 0 1 0 0
1 0 1 1 0 0 0 0 1 0
0 0 0 1 0 1 0 1 1 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 1 1 0 1
0 0 1 0 1 0 0 0 1 1
0 0 0 0 0 0 1 1 0 1
0 0 0 0 0 0 0 1 1 0
```

(140 croisements)

Σ dimensions efficaces

: 67

après 2"42

de CPU 360/75

Avec l'algorithme 3 modifié, nous obtenons la matrice :

```
0 1 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
1 1 1 1 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0 1 0
0 0 1 1 1 0 0 1 0 0
0 0 0 0 1 1 0 0 1 0
0 0 0 0 0 1 0 1 0 0
0 1 0 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 1 1 0
0 0 1 0 0 0 0 1 1 1
0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 1 1 1
```

(155 croisements)

Σ dimensions efficaces

: 67

après 1'20"

de CPU 360/75

toujours en partant de la matrice BQ
Si nous appliquons l'algorithme 1 de réduction des dimensions efficaces, nous obtenons la matrice :

1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0
1 0 0 0 0 1 0 0 0 0
0 0 1 1 0 0 1 1 0 0
0 0 0 0 1 1 0 0 1 0
0 0 1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 1 0

(167 croisements)

<figure><img src="image_25.png" /></figure>

Σ dimensions efficaces : 65

Sup. Dimensions efficaces : 8

après 1'57" de CPU
360/75

## 2°/ - Acroissement_de_laontimension

Au vu des résultats précédents, il apparaît que l'algorithme 1 donne les meilleurs résultats pour un temps correct, et que les algorithmes 1 et 3 modifié sont déjà très longs pour n=12.
L'algorithme 4 quant à lui donne des résultats honnêtes pour un temps très rapide.

### a) matrice tirée au sort

Nous avons essayé l'algorithme 1 dans un premier cas en tirant au sort une matrice 49x49 : CO avec 10 % d'éléments non nuls.
CO :

<figure><img src="image_26.png" /></figure>

CR :

<figure><img src="image_27.png" /></figure>

CQ :
matrice tirée
au sort
(49x49)
(10 %
d'éléments
non nuls)

CR :
réordonnée
par l'algorithme 3
bande supérieure
= bande inférieure
= 27
résultat peu
interessant
temps CP 360/91 9"
nous avons appliqué l'algorithme 2 à la matrice :

<figure><img src="image_28.png" /></figure>

(4 %
d'éléments
non nuls)

et nous avons obtenu la matrice :

<figure><img src="image_29.png" /></figure>

en 4"3
de 360/75

(on note que
la matrice IR
est non régulière).
Les résultats sont donc assez décevants, et si on devait résoudre le système linéaire CQ.x=b par la méthode de Gauss, il ne sera pas plus avantageux de résoudre :

```
CR.x=b
```

Ceci vient du fait que la matrice CQ est tirée au sort, et en fait dans de pareils cas, on ne peut pas espérer vraiment réduire la "bande" de la matrice (¹).

b) cas d'une matrice régulière "brouillée"

On part de la matrice 49x49 dont la diagonale principale est pleine, ainsi que les 5 diagonales inférieures, et les 3 diagonales supérieures. Soit EQ cette matrice.

Comme dans A 2°, on tire au sort deux permutations de `[1,49]`, et on obtient la matrice ER : "brouillée" en ordonnant les lignes et les colonnes de EQ suivant ces deux permutations.

<footnote>(¹) C'est dans le cas où on veut utiliser les programmes d'élimination de Gauss tenant compte de la bande, au moment de la factorisation, en effet, tout ce qui est en dehors de la bande reste nul.</footnote>
ER :

<figure><img src="image_30.png" /></figure>

matrice initiale
Place mémoire à
réserver pour ré-
soudre ER,x=b
par la méthode de
Gauss : 2401 mots.

en appliquant l'algorithme 3, on obtient :

EW :

<figure><img src="image_31.png" /></figure>

EW :
Matrice ER. réor-
donnée par l'al-
gorithme 3 en
8"10 de 360/91

(environ 2' de
360/75) Place
mémoire à réser-
ver pour résou-
dre un système
linéaire

EW.x=b

par la méthode
de Gauss (bande)
1098 mots.
en appliquant l'algorithme 2 à la matrice ER on obtient la
matrice suivante :

<figure><img src="image_32.png" /></figure>

en 1.1. Secondes
de 360/75.

la place mémoire occupée pour une résolution du système linéaire
par Gauss (bande) serait de 1033 mots.

Matrice régulière brouillée 121x121

Nous sommes partis de la matrice EQ (121x121), ayant 5
diagonales inférieures, 3 supérieures et la diagonale principale
pleine : et nous l'avons brouillée en tirant au sort deux permu-
tations H₁ et H₂ des nombres (1,...,121).
La matrice brouillée $\mathbf{EQ} [\mathbf{H}^1; \mathbf{H}^2] \text{ possédait la caractéristique suivante : } \text{sup (dim efficace en ligne : 117)}.$

En réordonnant HR par l'algorithme 2, on obtient en 12"37 de 360/75, une matrice HS qui a seulement 12 diagonales inférieures et 10 supérieures non entièrement nulles (plus la diagonale principale).

Pour résoudre un système linéaire de matrice HR, on occupe en mémoire 14.641 mots.

Pour résoudre le système correspondant pour HS on peut utiliser la méthode de Gauss bande, occupant seulement 2728 mots en mémoire.

Le rapport du nombre d'opérations à effectuer dans les deux cas est de l'ordre de 1 à 10.

Lorsqu'on part d'une matrice régulière que l'on brouille donc une matrice creuse ayant une certaine régularité, l'algorithme 2 donne un moyen **très performant** de réduire l'encombrement mémoire et les temps de calculs pour résoudre par exemple un système linéaire.

Si on a plusieurs systèmes linéaires à résoudre avec la même matrice, alors on peut essayer d'affiner le résultat avec l'algorithme 3.

Pour les matrices non symétriques, il semble bien que l'algorithme 3, heuristique, soit le plus intéressant, car il diminue de façon appréciable à la fois la somme des dimensions efficaces en ligne et le nombre des croisements. Pour les temps machine 30 à 50 fois plus grand, l'algorithme 1 de réduction des dimensions efficaces donne rarement de meilleurs résultats, et l'algorithme 3 modifié, des résultats toujours plus mauvais.

### C - Cas des matrices symétriques

#### 1° - Comparaison des diverses méthodes sur un cas particulier :

Nous allons comparer les diverses méthodes proposées à partir d'un exemple.
on considère le graphe

<figure><img src="image_33.png" /></figure>

(les voisins du noeud n° 5 sont les noeuds 3,6,8,11)

dont la matrice est

$$ \mathbf{AQ} = \begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \end{bmatrix} $$

(en posant $p_o=1,2,...,12$)

$$ f_1(p_o) = 112 $$

$$ f_2(p_o) = 82 $$

$$ f_3(p_o) = 68 \quad (\text{bande}=5) $$

$$ f_4(p_o) = 47 $$

$$ f_5(p_o) = 173 $$

On constate qu'une prenant $p_1=1,5,2,9,6,3,10,7,4,11,8,12$ on obtient la matrice $AQ [p_1 ; p_1]$ :

$$ \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & 0 & 1 & 1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} $$

$$ f_1(p_1) = 88 $$

$$ f_2(p_1) = 68 $$

$$ f_3(p_1) = 55 \quad (\text{bande}=4) $$

$$ f_4(p_1) = 40 $$

$$ f_5(p_1) = 124 $$

en fait $AQ [p_1 ; p_1]$ correspond au même maillage numéroté de la façon suivante :
<table><caption>Fig. 14 : Comparaison des divers algorithmes dans un cas particulier (matrice symétrique 12x12).</caption><tr><td>Algorithmes</td><td>Résultat donne après la convergence</td><td>Critère</td><td>Temps C.P. 360/75/(APL)</td><td>Remarque</td></tr><tr><td>3. De "pénalisation par la distance à la diagonale"</td><td>p<sub>0</sub></td><td>heuristique</td><td>0.19"</td><td>aucun progrès</td></tr><tr><td>3. "pénalisation par le nb de zeros séparant de la diagonale".</td><td>p<sub>1</sub></td><td>heuristique</td><td>37"</td><td>succès</td></tr><tr><td>Rosen</td><td>p<sub>0</sub></td><td>f<sub>3</sub></td><td>6"</td><td>aucun progrès</td></tr><tr><td>Rosen modifié</td><td>p<sub>0</sub></td><td>f<sub>4</sub></td><td>5"</td><td>aucun progrès</td></tr><tr><td>Cuthill et Mc Kee</td><td>p<sub>3</sub></td><td>heuristique</td><td>0.32"</td><td>optimum non obtenu</td></tr><tr><td>Algorithme de réduction par des transpositions</td><td>p<sub>1</sub></td><td>f<sub>1</sub></td><td>1' 3"13</td><td>succès</td></tr><tr><td>"</td><td>p<sub>2</sub></td><td>f<sub>2</sub></td><td>46"</td><td>f<sub>2</sub>'p<sub>2</sub>)=f<sub>2</sub>(p<sub>1</sub>)</td></tr><tr><td>"</td><td>p<sub>0</sub></td><td>f<sub>5</sub></td><td>4' de 91"</td><td>aucun progrès</td></tr></table>
<figure><img src="image_34.png" /></figure>

on s'attendait à ce résultat, car Cuthill et Mc Kee avaient montré que $p_o$ était un "optimum local" pour le critère $f_3$ (utilisé dans l'algorithme de Rosen).

Nous avons essayé en prenant comme point de départ $p_o$ de voir si on arrivait à améliorer les critères, avec les différents algorithmes. Fig. 14.

$P_4$ est la permutation correspondant à la rémunération suivante du maillage :

<figure><img src="image_35.png" /></figure>

$$f_1(p_4) = 90$$

$$f_2(p_4) = 70$$

$$f_3(p_4) = 57$$

$$f_4(p_4) = 41$$

$$f_5(p_4) = 131$$
$p_3$ est la permutation correspondant à la numérotation suivante du maillage :

<figure><img src="image_36.png" /></figure>

$$f_1(p_3) = 98 \quad f_3(p_3) = 62$$

$$f_2(p_3) = 72 \quad f_4(p_3) = 42$$

$$f_5(p_3) = 156$$

elle est obtenue par l'algorithme de Cuthill et Mc Kee, partant de $p_0$ et du noeud N° 1 mais si on partait d'une autre permutation on pourrait aussi bien obtenir $p_1$. $p_3$ est plus mauvais que $p_1$ à tous les points de vue.

Au vu des résultats on est amené à la remarque suivante : pour minimiser le critère $f_3$ ou $f_4$, il est préférable d'essayer de trouver une suite de transpositions minimisante pour les critères $f_1$ ou $f_2$. C'est en ce sens que l'on peut dire que $f_1$ et $f_2$ sont "meilleurs" que $f_3$ et $f_4$.

Pour nous rendre compte du caractère non "quasi-convexe" des critères, nous avons procédé à plusieurs tirages au sort de la numérotation du même maillage, et en utilisant les algorithmes, de voir à quels "optima locaux" on arrivait. Toutes les numérotations finales obtenues sont des "optima locaux" pour le critère qu'elles cherchent à minimiser.
<table><caption>Fig. 15 : Influence du "point" de départ, selon les critères, sur l'"optimum local" obtenu.</caption><thead><tr><th>essai<br>N°</th><th>critère<br>utilisé</th><th>numérotation<br>initiale</th><th>f<sub>1</sub></th><th>f<sub>2</sub></th><th>numérotation<br>finale</th><th>f<sub>1</sub></th><th>f<sub>2</sub></th><th>temps<br>CPV 360/75</th><th>f<sub>4</sub></th><th>algorithme</th></tr></thead><tbody><tr><td>1</td><td>f<sub>1</sub></td><td>1 7 10 4<br>9 8 3 6<br>2 5 12 11</td><td>133</td><td>105</td><td>3 6 9 12<br>1 4 7 10<br>2 5 8 11</td><td>90</td><td>71</td><td>41"54</td><td></td><td>réduction de<br>zone efficace</td></tr><tr><td>2</td><td>f<sub>1</sub></td><td>1 4 6 10<br>3 12 2 11<br>7 9 8 5</td><td>146</td><td>102</td><td>1 4 6 10<br>2 5 8 11<br>3 7 9 12</td><td>88</td><td>70</td><td>36" 4</td><td></td><td>"</td></tr><tr><td>3</td><td>f<sub>1</sub></td><td>11 8 4 3<br>10 2 12 5<br>1 6 9 7</td><td>135</td><td>101</td><td>4 6 10 12<br>1 5 7 11<br>2 3 8 9</td><td>90</td><td>69</td><td>39"19</td><td></td><td>"</td></tr><tr><td>4</td><td>f<sub>1</sub></td><td>12 11 3 6<br>7 2 9 5<br>4 10 1 8</td><td>134</td><td>100</td><td>12 11 6 5<br>10 8 7 2<br>9 4 3 1</td><td>97</td><td>73</td><td>38"46</td><td></td><td>"</td></tr><tr><td>5</td><td>f<sub>1</sub></td><td>3 8 4 5<br>1 9 11 6<br>7 12 10 2</td><td>146</td><td>103</td><td>12 10 7 4<br>11 8 5 2<br>9 6 3 1</td><td>88</td><td>68</td><td>40" 4</td><td></td><td>"</td></tr><tr><td>6</td><td>f<sub>2</sub></td><td>6 2 12 1<br>3 11 4 10<br>5 7 8 9</td><td>146</td><td>99</td><td>9 6 2 1<br>11 8 5 3<br>12 10 7 4</td><td>97</td><td>68</td><td>1' 4" 9</td><td>40</td><td>"</td></tr><tr><td>7</td><td>f<sub>2</sub></td><td>2 11 6 7<br>3 12 10 4<br>1 5 9 8</td><td>145</td><td>98</td><td>2 5 10 12<br>3 4 8 11<br>1 6 7 9</td><td>109</td><td>69</td><td>48"23</td><td>40</td><td>"</td></tr><tr><td>8</td><td>f<sub>2</sub></td><td>10 12 2 7<br>9 8 3 5<br>1 4 6 11</td><td>134</td><td>101</td><td>9 7 3 1<br>11 8 5 2<br>12 10 6 4</td><td>90</td><td>68</td><td>42" 6</td><td>40</td><td>"</td></tr><tr><td>9</td><td>f<sub>2</sub></td><td>9 10 2 7<br>12 6 8 1<br>3 5 11 4</td><td>134</td><td>104</td><td>12 10 6 4<br>11 7 5 3<br>9 8 2 1</td><td>98</td><td>68</td><td>52"22</td><td>40</td><td>"</td></tr><tr><td>10</td><td>f<sub>2</sub></td><td>4 3 10 12<br>8 9 11 6<br>1 7 2 5</td><td>123</td><td>99</td><td>12 8 5 2<br>11 9 4 3<br>10 7 6 1</td><td>98</td><td>70</td><td>36"39</td><td>41</td><td>"</td></tr><tr><td>11</td><td>f<sub>4</sub></td><td>8 1 7 4<br>5 9 10 2<br>12 6 11 3</td><td>59</td><td>104</td><td>8 1 7 4<br>5 9 10 2<br>12 6 11 3</td><td>104</td><td>4"58<br>(pas d'amélioration)</td><td>59</td><td>Rosen modifié</td><td></td></tr><tr><td>12</td><td>f<sub>4</sub></td><td>5 7 3 10<br>12 11 6 1<br>2 4 9 8</td><td>60</td><td></td><td>9 5 8 7<br>4 1 6 11<br>2 3 10 12</td><td>83</td><td>15"50</td><td>48</td><td></td><td>"</td></tr><tr><td>13</td><td>f<sub>4</sub></td><td>5 4 7 2<br>3 11 10 8<br>6 9 1 12</td><td>63</td><td></td><td>10 12 9 2<br>11 3 5 8<br>6 7 1 4</td><td>95</td><td>9"</td><td>55</td><td></td><td>"</td></tr><tr><td>14</td><td>f<sub>4</sub></td><td>10 7 9 2<br>11 12 5 1<br>3 4 6 8</td><td>51</td><td></td><td>10 11 9 2<br>12 7 5 1<br>3 4 6 8</td><td>91</td><td>6"43</td><td>50</td><td></td><td>"</td></tr><tr><td>15</td><td>f<sub>2</sub></td><td>12 8 5 2<br>11 9 4 3<br>10 7 6 1</td><td>70</td><td></td><td>12 10 5 2<br>11 8 4 3<br>9 7 6 1</td><td>69</td><td></td><td></td><td></td><td>glissements<br>systématiques</td></tr><tr><td>16</td><td>f<sub>5</sub></td><td>12 8 5 2<br>11 9 4 3<br>10 7 6 1</td><td>f<sub>5</sub> = 173</td><td></td><td>12 9 6 3<br>11 8 5 2<br>10 7 4 1</td><td>f<sub>5</sub> = 131</td><td>19' de 91</td><td></td><td></td><td>glissements<br>systématiques</td></tr></tbody></table>
Le dernier exemple est prohibitivement long, car le calcul des croisements est très long, or à chaque essai on fait un calcul de croisements !

Mais il n'y a pas de regrets à avoir car le critère $f_5$ n'est pas plus "quasi-convexe" que les autres (on a exhibé des "optima-locaux" non "globaux").

Par conséquent parmi les critères considérés, les critères $f_1$ ou $f_2$ sont à peu près analogues et nettement supérieurs aux critères $f_3$ et $f_4$ quant aux résultats obtenus, et au critère $f_5$ quant au temps machine.

L'algorithme de réduction par des transpositions successives est assez performant, en ce sens qu'il trouve rapidement à chaque étape une transposition minimisante, et que lorsqu'il a convergé, dans aucun des cas envisagés, une transposition quelconque n'améliorait le résultat.

Evidemment ces critères ne sont pas "quasi-convexes", mais du moins les optima locaux ne sont-ils pas très loin dans l'exemple étudié de l'optimum global.

Il semble que la tactique qui consiste à appliquer d'abord l'algorithme (heuristique) de Cuthill et Mc Kee, puis l'algorithme de réduction, avec le critère $f_2$ par exemple soit bonne à tous les points de vue lorsqu'on veut une solution presque optimale.

## 2° / - Essais_lorsque_la_taille_de_la matrice_croît

Lorsqu'on s'intéresse aux problèmes de réduction de taille mémoire pour les matrices d'éléments finis, on a affaire à de beaucoup plus grandes valeurs pour N. La question du temps machine devient alors prédominante, car l'objectif réel est de diminuer le temps machine que coûte la résolution globale du problème d'éléments finis.

La remunération des noeuds permet d'obtenir une matrice bande, et une factorisée de Choleski beaucoup plus creuse, ce qui gagne beaucoup de temps.

Mais évidemment il ne faut pas que la rémunération prenne trop de temps.

Pour une étude détaillée du rapport entre le temps (machine) de résolution et le temps (machine) de numérotation, nous renvoyons à GEORGE [6].
En fait, lorsque les exemples ont une taille suffisante, le gain de temps procuré par une renumérotation en utilisant l'algorithme de Cuthill et Mc Kee est très grand, et on ne gagne pas tellement à essayer d'améliorer la numérotation par un algorithme systématique, par rapport au temps que celà coûte.

Dans ce qui suit nous allons donner des résultats de rénumérotation par l'algorithme de Cuthill et Mc Kee.

Les résultats suivants concernent la numérotation de la triangulation :

<figure><img src="image_37.png" /></figure>

On a donc $N=n^2$ et on a fait plusieurs essais en faisant varier n, en tirant au sort la numérotation de départ, et en essayant de la renuméroter par l'algorithme dérivé de Cuthill et Mc Kee, (non de degré minimal).
1°/ n=5
N=25 noeuds

10 13 18 6 14 numérotation initiale
20 12 17 5 24
23 22 15 1 21
25 16 2 3 11
8 7 4 9 19

1 2 5 9 14 numérotation donnée par l'algorithme.
3 4 7 11 17
6 8 12 16 21
10 13 18 20 24
15 19 22 23 25

Nous donnons également les matrices correspondant à ces maillages.
2°/ n=7

N=49 noeuds

<table><tr><td>19</td><td>16</td><td>47</td><td>1</td><td>45</td><td>5</td><td>32</td></tr><tr><td>30</td><td>49</td><td>38</td><td>39</td><td>35</td><td>22</td><td>8</td></tr><tr><td>15</td><td>6</td><td>31</td><td>20</td><td>42</td><td>11</td><td>23</td></tr><tr><td>33</td><td>43</td><td>40</td><td>10</td><td>9</td><td>27</td><td>18</td></tr><tr><td>37</td><td>28</td><td>26</td><td>4</td><td>12</td><td>48</td><td>17</td></tr><tr><td>41</td><td>2</td><td>29</td><td>3</td><td>21</td><td>25</td><td>24</td></tr><tr><td>44</td><td>13</td><td>14</td><td>46</td><td>36</td><td>7</td><td>34</td></tr><tr><td>1</td><td>2</td><td>4</td><td>7</td><td>12</td><td>18</td><td>25</td></tr><tr><td>3</td><td>5</td><td>8</td><td>11</td><td>17</td><td>24</td><td>32</td></tr><tr><td>6</td><td>9</td><td>13</td><td>16</td><td>23</td><td>31</td><td>38</td></tr><tr><td>10</td><td>14</td><td>19</td><td>22</td><td>30</td><td>37</td><td>43</td></tr><tr><td>15</td><td>20</td><td>26</td><td>29</td><td>36</td><td>42</td><td>46</td></tr><tr><td>21</td><td>27</td><td>33</td><td>35</td><td>40</td><td>44</td><td>48</td></tr><tr><td>28</td><td>34</td><td>39</td><td>41</td><td>45</td><td>47</td><td>49</td></tr></table>

numérotation initiale

numérotation réordonnée
par l'algorithme.
$3^{\circ}/ n=11, N=121$

Triangulation à 121 noeuds

<table><tbody><tr><td>61</td><td>28</td><td>119</td><td>114</td><td>22</td><td>55</td><td>66</td><td>9</td><td>46</td><td>13</td><td>37</td></tr><tr><td>79</td><td>82</td><td>30</td><td>15</td><td>42</td><td>95</td><td>25</td><td>19</td><td>103</td><td>44</td><td>8</td></tr><tr><td>39</td><td>41</td><td>20</td><td>4</td><td>99</td><td>65</td><td>27</td><td>26</td><td>6</td><td>121</td><td>63</td></tr><tr><td>70</td><td>60</td><td>12</td><td>23</td><td>88</td><td>105</td><td>10</td><td>71</td><td>18</td><td>91</td><td>33</td></tr><tr><td>77</td><td>76</td><td>117</td><td>38</td><td>106</td><td>109</td><td>35</td><td>17</td><td>86</td><td>80</td><td>21</td></tr><tr><td>85</td><td>16</td><td>83</td><td>108</td><td>116</td><td>72</td><td>113</td><td>7</td><td>5</td><td>31</td><td>112</td></tr><tr><td>87</td><td>59</td><td>49</td><td>81</td><td>100</td><td>118</td><td>120</td><td>64</td><td>104</td><td>6</td><td>1</td></tr><tr><td>50</td><td>34</td><td>101</td><td>14</td><td>69</td><td>93</td><td>62</td><td>40</td><td>51</td><td>92</td><td>11</td></tr><tr><td>110</td><td>2</td><td>90</td><td>115</td><td>102</td><td>96</td><td>68</td><td>58</td><td>74</td><td>54</td><td>36</td></tr><tr><td>29</td><td>24</td><td>111</td><td>3</td><td>32</td><td>89</td><td>97</td><td>98</td><td>43</td><td>78</td><td>47</td></tr><tr><td>52</td><td>48</td><td>57</td><td>53</td><td>84</td><td>45</td><td>107</td><td>94</td><td>75</td><td>73</td><td>56</td></tr><tr><td>0</td><td>33</td><td>25</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>121</td><td>119</td><td>116</td><td>112</td><td>107</td><td>101</td><td>94</td><td>90</td><td>82</td><td>72</td><td>62</td></tr><tr><td>120</td><td>117</td><td>113</td><td>108</td><td>102</td><td>95</td><td>86</td><td>80</td><td>71</td><td>60</td><td>51</td></tr><tr><td>118</td><td>114</td><td>109</td><td>103</td><td>96</td><td>87</td><td>77</td><td>69</td><td>59</td><td>49</td><td>41</td></tr><tr><td>115</td><td>110</td><td>104</td><td>97</td><td>88</td><td>78</td><td>67</td><td>57</td><td>48</td><td>39</td><td>32</td></tr><tr><td>111</td><td>105</td><td>98</td><td>89</td><td>79</td><td>68</td><td>56</td><td>46</td><td>38</td><td>30</td><td>24</td></tr><tr><td>106</td><td>99</td><td>91</td><td>81</td><td>70</td><td>58</td><td>47</td><td>37</td><td>29</td><td>22</td><td>17</td></tr><tr><td>100</td><td>92</td><td>83</td><td>73</td><td>61</td><td>50</td><td>40</td><td>31</td><td>23</td><td>16</td><td>11</td></tr><tr><td>93</td><td>84</td><td>74</td><td>63</td><td>52</td><td>42</td><td>33</td><td>25</td><td>18</td><td>12</td><td>7</td></tr><tr><td>85</td><td>75</td><td>64</td><td>53</td><td>43</td><td>34</td><td>26</td><td>19</td><td>13</td><td>8</td><td>4</td></tr><tr><td>76</td><td>65</td><td>54</td><td>44</td><td>35</td><td>27</td><td>20</td><td>14</td><td>9</td><td>5</td><td>2</td></tr><tr><td>66</td><td>55</td><td>45</td><td>36</td><td>28</td><td>21</td><td>15</td><td>10</td><td>6</td><td>3</td><td>1</td></tr><tr><td>0</td><td>17</td><td>0</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

Triangulation avec une numérotation quelconque.

Triangulation réordonnée par l'algorithme en 17" de temps machine (IBM 360/75).

$4^{\circ}/ n=15, N=225$

Triangulation à 225 noeuds

<table><tbody><tr><td>216</td><td>85</td><td>59</td><td>158</td><td>72</td><td>209</td><td>166</td><td>194</td><td>190</td><td>50</td><td>52</td><td>165</td><td>70</td><td>168</td><td>207</td></tr><tr><td>132</td><td>220</td><td>169</td><td>172</td><td>201</td><td>146</td><td>111</td><td>176</td><td>74</td><td>118</td><td>147</td><td>180</td><td>65</td><td>24</td><td>135</td></tr><tr><td>157</td><td>196</td><td>96</td><td>88</td><td>108</td><td>84</td><td>148</td><td>25</td><td>134</td><td>139</td><td>107</td><td>144</td><td>80</td><td>159</td><td>106</td></tr><tr><td>4</td><td>75</td><td>128</td><td>48</td><td>49</td><td>15</td><td>27</td><td>99</td><td>109</td><td>6</td><td>217</td><td>68</td><td>56</td><td>46</td><td>45</td></tr><tr><td>100</td><td>20</td><td>222</td><td>13</td><td>186</td><td>203</td><td>58</td><td>3</td><td>91</td><td>185</td><td>205</td><td>69</td><td>7</td><td>212</td><td>63</td></tr><tr><td>103</td><td>161</td><td>64</td><td>192</td><td>8</td><td>188</td><td>2</td><td>55</td><td>110</td><td>206</td><td>18</td><td>10</td><td>47</td><td>26</td><td>152</td></tr><tr><td>204</td><td>221</td><td>30</td><td>17</td><td>51</td><td>104</td><td>179</td><td>121</td><td>39</td><td>16</td><td>87</td><td>57</td><td>133</td><td>38</td><td>23</td></tr><tr><td>142</td><td>137</td><td>62</td><td>126</td><td>34</td><td>129</td><td>93</td><td>164</td><td>40</td><td>37</td><td>43</td><td>101</td><td>53</td><td>171</td><td>36</td></tr><tr><td>149</td><td>125</td><td>208</td><td>79</td><td>127</td><td>136</td><td>117</td><td>98</td><td>162</td><td>223</td><td>123</td><td>141</td><td>202</td><td>41</td><td>31</td></tr><tr><td>28</td><td>124</td><td>200</td><td>19</td><td>225</td><td>138</td><td>35</td><td>184</td><td>130</td><td>78</td><td>12</td><td>92</td><td>86</td><td>154</td><td>82</td></tr><tr><td>173</td><td>218</td><td>119</td><td>214</td><td>89</td><td>94</td><td>112</td><td>66</td><td>73</td><td>102</td><td>77</td><td>114</td><td>105</td><td>213</td><td>198</td></tr><tr><td>113</td><td>11</td><td>150</td><td>155</td><td>42</td><td>29</td><td>22</td><td>145</td><td>160</td><td>211</td><td>1</td><td>219</td><td>177</td><td>122</td><td>199</td></tr><tr><td>83</td><td>90</td><td>67</td><td>182</td><td>210</td><td>71</td><td>116</td><td>14</td><td>193</td><td>167</td><td>60</td><td>115</td><td>195</td><td>224</td><td>170</td></tr><tr><td>54</td><td>181</td><td>44</td><td>143</td><td>174</td><td>187</td><td>95</td><td>153</td><td>215</td><td>9</td><td>156</td><td>120</td><td>140</td><td>33</td><td>189</td></tr><tr><td>183</td><td>151</td><td>163</td><td>81</td><td>191</td><td>178</td><td>197</td><td>32</td><td>97</td><td>61</td><td>131</td><td>175</td><td>5</td><td>76</td><td>21</td></tr><tr><td>48</td><td>0</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>225</td><td>223</td><td>220</td><td>218</td><td>214</td><td>208</td><td>201</td><td>195</td><td>186</td><td>180</td><td>169</td><td>159</td><td>147</td><td>134</td><td>120</td></tr><tr><td>224</td><td>221</td><td>216</td><td>212</td><td>207</td><td>200</td><td>192</td><td>185</td><td>175</td><td>168</td><td>156</td><td>146</td><td>133</td><td>119</td><td>105</td></tr><tr><td>222</td><td>217</td><td>211</td><td>205</td><td>199</td><td>191</td><td>182</td><td>174</td><td>163</td><td>155</td><td>142</td><td>131</td><td>117</td><td>104</td><td>91</td></tr><tr><td>219</td><td>213</td><td>206</td><td>198</td><td>190</td><td>181</td><td>171</td><td>162</td><td>150</td><td>141</td><td>127</td><td>115</td><td>102</td><td>90</td><td>78</td></tr><tr><td>215</td><td>209</td><td>202</td><td>193</td><td>183</td><td>172</td><td>160</td><td>149</td><td>136</td><td>126</td><td>111</td><td>100</td><td>88</td><td>77</td><td>66</td></tr><tr><td>210</td><td>203</td><td>194</td><td>184</td><td>173</td><td>161</td><td>148</td><td>135</td><td>121</td><td>110</td><td>96</td><td>86</td><td>75</td><td>65</td><td>55</td></tr><tr><td>204</td><td>196</td><td>187</td><td>176</td><td>164</td><td>151</td><td>137</td><td>122</td><td>106</td><td>95</td><td>82</td><td>73</td><td>63</td><td>54</td><td>45</td></tr><tr><td>197</td><td>188</td><td>177</td><td>165</td><td>152</td><td>138</td><td>123</td><td>107</td><td>92</td><td>81</td><td>69</td><td>61</td><td>52</td><td>44</td><td>36</td></tr><tr><td>189</td><td>178</td><td>166</td><td>153</td><td>139</td><td>124</td><td>108</td><td>93</td><td>79</td><td>68</td><td>57</td><td>50</td><td>42</td><td>35</td><td>28</td></tr><tr><td>179</td><td>167</td><td>154</td><td>140</td><td>125</td><td>109</td><td>94</td><td>80</td><td>67</td><td>56</td><td>46</td><td>40</td><td>33</td><td>27</td><td>21</td></tr><tr><td>170</td><td>157</td><td>143</td><td>128</td><td>112</td><td>97</td><td>83</td><td>70</td><td>58</td><td>47</td><td>37</td><td>31</td><td>25</td><td>20</td><td>15</td></tr><tr><td>158</td><td>144</td><td>129</td><td>113</td><td>98</td><td>84</td><td>71</td><td>59</td><td>48</td><td>38</td><td>29</td><td>23</td><td>18</td><td>14</td><td>10</td></tr><tr><td>145</td><td>130</td><td>114</td><td>99</td><td>85</td><td>72</td><td>60</td><td>49</td><td>39</td><td>30</td><td>22</td><td>16</td><td>12</td><td>9</td><td>6</td></tr><tr><td>132</td><td>116</td><td>101</td><td>87</td><td>74</td><td>62</td><td>51</td><td>41</td><td>32</td><td>24</td><td>17</td><td>11</td><td>7</td><td>5</td><td>3</td></tr><tr><td>118</td><td>103</td><td>89</td><td>76</td><td>64</td><td>53</td><td>43</td><td>34</td><td>26</td><td>19</td><td>13</td><td>8</td><td>4</td><td>2</td><td>1</td></tr><tr><td>49</td><td>33</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

avec une numérotation brouillée (bande de la matrice = 219).

réordonnée par l'algorithme (bande=17) 41" de temps machine (360/75).

Dans ce dernier exemple la factorisée de Choleski comporterait

- pour la numérotation brouillée : 18822 termes non nuls

- pour la numérotation réordonnée : 2639 termes non nuls.
$5^{\circ}/ n=19, N=361.$

Triangulation avec 361 nœuds

<table><tbody><tr><td>120</td><td>341</td><td>255</td><td>114</td><td>172</td><td>101</td><td>235</td><td>274</td><td>5</td><td>216</td><td>64</td><td>221</td><td>14</td><td>227</td><td>161</td><td>67</td><td>123</td><td>292</td><td>233</td></tr><tr><td>86</td><td>259</td><td>13</td><td>359</td><td>308</td><td>223</td><td>335</td><td>338</td><td>247</td><td>242</td><td>291</td><td>220</td><td>139</td><td>117</td><td>165</td><td>322</td><td>278</td><td>100</td><td>321</td></tr><tr><td>281</td><td>346</td><td>316</td><td>130</td><td>28</td><td>125</td><td>108</td><td>294</td><td>188</td><td>75</td><td>157</td><td>344</td><td>74</td><td>357</td><td>264</td><td>22</td><td>30</td><td>204</td><td>78</td></tr><tr><td>142</td><td>158</td><td>212</td><td>66</td><td>177</td><td>46</td><td>106</td><td>83</td><td>224</td><td>143</td><td>339</td><td>240</td><td>215</td><td>180</td><td>141</td><td>238</td><td>124</td><td>351</td><td>248</td></tr><tr><td>183</td><td>94</td><td>76</td><td>91</td><td>29</td><td>90</td><td>2</td><td>288</td><td>218</td><td>260</td><td>121</td><td>175</td><td>309</td><td>51</td><td>9</td><td>301</td><td>169</td><td>324</td><td>232</td></tr><tr><td>254</td><td>26</td><td>164</td><td>138</td><td>31</td><td>61</td><td>271</td><td>196</td><td>48</td><td>79</td><td>225</td><td>330</td><td>140</td><td>126</td><td>211</td><td>217</td><td>287</td><td>361</td><td>163</td></tr><tr><td>318</td><td>69</td><td>111</td><td>256</td><td>282</td><td>317</td><td>243</td><td>347</td><td>104</td><td>332</td><td>337</td><td>342</td><td>194</td><td>122</td><td>297</td><td>34</td><td>152</td><td>230</td><td>286</td></tr><tr><td>85</td><td>319</td><td>355</td><td>92</td><td>244</td><td>315</td><td>99</td><td>147</td><td>27</td><td>112</td><td>261</td><td>102</td><td>273</td><td>300</td><td>345</td><td>47</td><td>186</td><td>36</td><td>277</td></tr><tr><td>222</td><td>279</td><td>58</td><td>234</td><td>251</td><td>268</td><td>246</td><td>329</td><td>171</td><td>284</td><td>18</td><td>190</td><td>20</td><td>55</td><td>178</td><td>118</td><td>42</td><td>109</td><td>203</td></tr><tr><td>193</td><td>62</td><td>1</td><td>298</td><td>145</td><td>358</td><td>37</td><td>245</td><td>331</td><td>265</td><td>210</td><td>302</td><td>149</td><td>307</td><td>41</td><td>187</td><td>159</td><td>208</td><td>6</td></tr><tr><td>53</td><td>77</td><td>206</td><td>38</td><td>24</td><td>131</td><td>8</td><td>170</td><td>93</td><td>4</td><td>162</td><td>32</td><td>134</td><td>97</td><td>304</td><td>72</td><td>119</td><td>229</td><td>35</td></tr><tr><td>275</td><td>354</td><td>272</td><td>96</td><td>144</td><td>23</td><td>340</td><td>195</td><td>88</td><td>198</td><td>12</td><td>132</td><td>60</td><td>285</td><td>185</td><td>219</td><td>293</td><td>25</td><td>250</td></tr><tr><td>52</td><td>146</td><td>334</td><td>290</td><td>328</td><td>305</td><td>56</td><td>50</td><td>214</td><td>82</td><td>7</td><td>348</td><td>153</td><td>327</td><td>179</td><td>63</td><td>269</td><td>39</td><td>231</td></tr><tr><td>356</td><td>45</td><td>283</td><td>103</td><td>257</td><td>296</td><td>209</td><td>303</td><td>156</td><td>241</td><td>65</td><td>15</td><td>333</td><td>84</td><td>116</td><td>325</td><td>113</td><td>299</td><td>350</td></tr><tr><td>373</td><td>167</td><td>249</td><td>80</td><td>207</td><td>191</td><td>105</td><td>70</td><td>266</td><td>276</td><td>263</td><td>313</td><td>312</td><td>10</td><td>174</td><td>81</td><td>107</td><td>54</td><td>44</td></tr><tr><td>314</td><td>205</td><td>308</td><td>19</td><td>135</td><td>11</td><td>256</td><td>192</td><td>189</td><td>166</td><td>40</td><td>320</td><td>200</td><td>68</td><td>310</td><td>127</td><td>213</td><td>17</td><td>311</td></tr><tr><td>236</td><td>21</td><td>95</td><td>176</td><td>239</td><td>237</td><td>280</td><td>136</td><td>336</td><td>343</td><td>98</td><td>57</td><td>89</td><td>360</td><td>199</td><td>349</td><td>252</td><td>16</td><td>201</td></tr><tr><td>110</td><td>197</td><td>133</td><td>253</td><td>262</td><td>326</td><td>155</td><td>295</td><td>267</td><td>173</td><td>49</td><td>73</td><td>3</td><td>43</td><td>202</td><td>87</td><td>168</td><td>228</td><td>151</td></tr><tr><td>352</td><td>270</td><td>59</td><td>181</td><td>226</td><td>129</td><td>33</td><td>137</td><td>289</td><td>184</td><td>182</td><td>128</td><td>150</td><td>71</td><td>115</td><td>148</td><td>353</td><td>160</td><td>154</td></tr></tbody></table>

numérotation

brouillée

bande=358

48418 termes non

nuls dans la facto-
risée de Choleski.

1 36 36

<table><tbody><tr><td>1</td><td>3</td><td>6</td><td>10</td><td>15</td><td>21</td><td>28</td><td>36</td><td>45</td><td>55</td><td>66</td><td>78</td><td>91</td><td>105</td><td>120</td><td>136</td><td>153</td><td>171</td><td>190</td></tr><tr><td>2</td><td>4</td><td>7</td><td>12</td><td>18</td><td>25</td><td>33</td><td>42</td><td>52</td><td>63</td><td>75</td><td>88</td><td>102</td><td>117</td><td>133</td><td>150</td><td>168</td><td>187</td><td>207</td></tr><tr><td>5</td><td>8</td><td>11</td><td>16</td><td>22</td><td>29</td><td>38</td><td>48</td><td>59</td><td>71</td><td>84</td><td>98</td><td>113</td><td>129</td><td>146</td><td>164</td><td>183</td><td>203</td><td>222</td></tr><tr><td>9</td><td>13</td><td>17</td><td>23</td><td>30</td><td>37</td><td>47</td><td>58</td><td>70</td><td>83</td><td>97</td><td>112</td><td>128</td><td>145</td><td>163</td><td>182</td><td>202</td><td>221</td><td>239</td></tr><tr><td>14</td><td>19</td><td>24</td><td>31</td><td>39</td><td>46</td><td>56</td><td>68</td><td>81</td><td>95</td><td>110</td><td>126</td><td>143</td><td>161</td><td>180</td><td>200</td><td>219</td><td>237</td><td>254</td></tr><tr><td>20</td><td>26</td><td>32</td><td>40</td><td>49</td><td>57</td><td>67</td><td>79</td><td>92</td><td>106</td><td>121</td><td>137</td><td>154</td><td>172</td><td>192</td><td>211</td><td>229</td><td>246</td><td>262</td></tr><tr><td>27</td><td>34</td><td>41</td><td>50</td><td>60</td><td>69</td><td>80</td><td>93</td><td>107</td><td>122</td><td>138</td><td>155</td><td>173</td><td>191</td><td>209</td><td>226</td><td>243</td><td>259</td><td>274</td></tr><tr><td>35</td><td>43</td><td>51</td><td>61</td><td>72</td><td>82</td><td>94</td><td>108</td><td>123</td><td>139</td><td>156</td><td>174</td><td>193</td><td>210</td><td>227</td><td>242</td><td>258</td><td>273</td><td>287</td></tr><tr><td>44</td><td>53</td><td>62</td><td>73</td><td>85</td><td>96</td><td>109</td><td>124</td><td>140</td><td>157</td><td>175</td><td>194</td><td>212</td><td>228</td><td>244</td><td>257</td><td>271</td><td>284</td><td>296</td></tr><tr><td>54</td><td>54</td><td>74</td><td>86</td><td>99</td><td>111</td><td>125</td><td>141</td><td>158</td><td>176</td><td>195</td><td>213</td><td>230</td><td>245</td><td>260</td><td>272</td><td>285</td><td>297</td><td>307</td></tr><tr><td>65</td><td>76</td><td>87</td><td>100</td><td>114</td><td>127</td><td>142</td><td>159</td><td>177</td><td>196</td><td>214</td><td>231</td><td>247</td><td>261</td><td>275</td><td>286</td><td>298</td><td>308</td><td>317</td></tr><tr><td>77</td><td>89</td><td>101</td><td>115</td><td>130</td><td>144</td><td>160</td><td>178</td><td>197</td><td>215</td><td>232</td><td>248</td><td>263</td><td>276</td><td>288</td><td>299</td><td>309</td><td>318</td><td>326</td></tr><tr><td>90</td><td>103</td><td>116</td><td>131</td><td>147</td><td>162</td><td>179</td><td>198</td><td>216</td><td>233</td><td>249</td><td>264</td><td>277</td><td>289</td><td>300</td><td>310</td><td>319</td><td>327</td><td>334</td></tr><tr><td>104</td><td>118</td><td>132</td><td>148</td><td>165</td><td>181</td><td>193</td><td>217</td><td>234</td><td>250</td><td>265</td><td>278</td><td>290</td><td>301</td><td>311</td><td>320</td><td>328</td><td>335</td><td>341</td></tr><tr><td>119</td><td>134</td><td>149</td><td>166</td><td>184</td><td>201</td><td>218</td><td>235</td><td>251</td><td>266</td><td>279</td><td>291</td><td>302</td><td>312</td><td>321</td><td>329</td><td>336</td><td>342</td><td>347</td></tr><tr><td>135</td><td>151</td><td>167</td><td>185</td><td>204</td><td>220</td><td>236</td><td>252</td><td>267</td><td>280</td><td>292</td><td>303</td><td>313</td><td>322</td><td>330</td><td>337</td><td>343</td><td>348</td><td>352</td></tr><tr><td>152</td><td>169</td><td>186</td><td>205</td><td>223</td><td>238</td><td>253</td><td>268</td><td>281</td><td>293</td><td>304</td><td>314</td><td>323</td><td>331</td><td>338</td><td>344</td><td>349</td><td>353</td><td>356</td></tr><tr><td>170</td><td>188</td><td>206</td><td>224</td><td>240</td><td>255</td><td>269</td><td>282</td><td>294</td><td>305</td><td>315</td><td>324</td><td>332</td><td>339</td><td>345</td><td>350</td><td>354</td><td>357</td><td>359</td></tr><tr><td>189</td><td>208</td><td>225</td><td>241</td><td>256</td><td>270</td><td>283</td><td>295</td><td>306</td><td>316</td><td>325</td><td>333</td><td>340</td><td>346</td><td>351</td><td>355</td><td>358</td><td>360</td><td>361</td></tr></tbody></table>

réordonnée

bande=21 5157

termes non nuls

dans la factorisée

de Choleski

temps machine :

2' de 360/75.
## CONCLUSION GENERALE

Les résultats numériques montrent avec une grande force l'énorme disparité entre les temps-machines des divers algorithmes.

On trouve tout d'abord un bon algorithme heuristique : l'algorithme 2 qui (donne l'algorithme de Cuthill et Mc Kee, dans le cas symétrique). Cet algorithme donne dans un temps très rapide une réduction très appréciable de l'encombrement des matrices provenant d'une matrice régulière, dont les numérotations sont brouillées pour diverses raisons (ex : matrices d'éléments finis dans le cas symétrique).

On trouve ensuite (20 à 40 fois plus lent) un bon algorithme heuristique, l'algorithme 3, qui donne de meilleurs résultats que le précédent dans le cas où les matrices ont une structure vraiment aléatoire.

Enfin, si l'on cherche pour une raison ou pour une autre une solution plus "optimale", on dispose d'algorithmes 20 à 50 fois plus lent que le précédent qui peuvent améliorer localement une solution : l'algorithme 3 modifié, l'algorithme 1 et tous les algorithmes du même genre, qui font une recherche systématique avec un temps machine qui croît de la même façon, en se rappelant que de toutes façons on ne pourra jamais être certain d'avoir la solution du problème, sauf dans des cas bien particuliers.
BIBLIOGRAPHIE

I. ARANY, L. SZODA and W.F. MITH

[1] : An Improved Method for Reducing the Band-with of Sparse Symmetric Matrices. I.F.I.P. Congress, (August 1971).

A.R. CURTIS and J.K. REID

[2] : The solution of Large Sparse Unsymmetric Systems of Linear Equations. I.F.I.P. Congress, (August 1971).

E. CUTHILL and J. Mc KEE

[3] : Reducing the boundwidth of the sparse symmetric matrices"... Proc 24 TH National Conf. ACM, p. 69 (1969).

S.B. DEUTSCH and J. J. MARTIN

[4] : Operations and Research 1971. An ordering algorithm for Analysis of Data Aways.

B.M. IRONS

[5] : A Frontal solution method for finite element Analysis. Int. Journ. For Num. Meth. in Eng. Vol. 2, N° 1 1970, p. 5.3.

J. ALAN GEORGE

[6] : Computer Implementation of the Finite Element Method Computer Science Department. Stanford 1971.

D.J. ROSE and R. A. WILLOVGHBY

[7] : Sparse Matrices and their applications I.B.M. Research Symposia Series 1972.

R. ROSEN

[8] : Matrix Band-with Minimization. Proceedings - A.C.M. National Conference; (1968).

V.V. SHKURBA

[9] : Mathematical Processing of a Class of Biochemical Experiments. Kibernetika, Vol. 1, p. 62-67, (1965).
R.P. TEWARSON

[10] : Row-Column Permutations of Sparse Matrices. S.I.A.M. Rev. (1968).

R.A. WILLOUGHBY

[11]: Editor, I.B.M. Sparse Matrix Proceedings Thomas J. Watson Research Center Yorktown Mgts. 1968.

Pour un problème analogue : Optimization in Industries.
T.A.J. NICHOLSON Industrial Applications
Volume II p. 113-121 Longman, London 1971.

---