Terminaison des algorithmes itératifs parallèles asynchrones
Algorithmes parallèles asynchrones II - Implémentation

Dans un premier article [AF 1 385] on a considéré la résolution de deux types de problème pseudo-linéaire. Le premier problème est un problème univoque du type

où A est une matrice de dimension $M\in \mathbb{N}$ , ensemble des entiers naturels, G et U sont des vecteurs de dimension M et

Le second type de problème est multivoque car sa solution U est soumise à des contraintes inégalité du type

dans ce cas on est amené à résoudre le problème multivoque suivant

où U → Ψ(U) est la fonction indicatrice de l’ensemble convexe K définissant les contraintes, ∂Ψ(U) est le sous-différentiel de cette fonction indicatrice et vérifie la propriété importante d’être diagonal monotone.

La matrice A étant de grande dimension, dans chaque cas, la détermination de la solution consiste à résoudre un système algébrique de grande taille. On associe alors à chacun de ces systèmes non linéaires une équation de point fixe définie formellement par

cette dernière étant résolue par un algorithme parallèle asynchrone. Soit α un nombre entier naturel ; décomposons le vecteur $V\in \mathcal{E}\equiv {ℝ}^M$ et l’application de point fixe V → F(V) en α blocs de la façon suivante :

où l’on note $V_I\in {\mathcal{E}}_I$ , le bloc-composante de V pour $I\in \left\{1,\dots ,\mathrm{\hspace{0.17em}}\alpha \right\}$ , avec $\mathcal{E}={\displaystyle \prod _{I=1}^{\alpha }{\mathcal{E}}_I}$ , où ${\mathcal{E}}_I={ℝ}^{m_I}$ , avec ${\displaystyle \sum _{I=1}^{\alpha }{m}_I}=M$ , est un sous-espace de $\mathcal{E}$ . Soient ${\left|\mathrm{\hspace{0.17em}}\cdot \mathrm{\hspace{0.17em}}\right|}_I$ les normes définies dans ${\mathcal{E}}_I$ , l = 1, … , α.

Pour résoudre le problème de point fixe (5), on utilise les itérations parallèles asynchrones définies comme suit : soit $U^0\in \mathcal{E}$ donné ; alors, pour tout $r\in \mathbb{N}$ , U ^r+1 est défini récursivement par :

où

et $\forall k\in \left\{1,\dots ,\mathrm{\hspace{0.17em}}\alpha \right\}$ ,

Dans ce modèle mathématique de l’algorithme parallèle asynchrone, le parallélisme entre les processeurs est bien décrit par l’ensemble s(r) qui contient le numéro des composantes relaxées par chaque processeur de manière parallèle. De plus l’utilisation dans (7) de composantes retardées $U_k^{{\mathcal{K}}_k\left(r\right)}$ provenant de relaxations disponibles au début du calcul, avec ${\mathcal{K}}_k\left(r\right)$ satisfaisant (9), permet de modéliser un comportement non déterministe et n’implique pas d’inefficacité du schéma de calcul distribué considéré. Sur le plan pratique, et pour que ces méthodes soient le plus efficace possible, on effectue des relaxations en prenant les valeurs d’interaction $U_k^{{\mathcal{K}}_k\left(r\right)}$ les plus récentes disponibles calculées par les autres processeurs ; en fait ce choix s’effectue naturellement lorsque l’algorithme s’exécute sans que le programmeur n’ait à coder quoi que ce soit.

Pour analyser la convergence de ces méthodes itératives, on dispose de trois possibilités liées à des propriétés formellement distinctes

• une propriété de contraction de l’application de point fixe F soit par rapport à une norme vectorielle soit par rapport à une norme uniforme avec poids ;

• une propriété de convergence monotone qui est vérifiée uniquement pour le problème (1) puisque l’opérateur $V\to \mathcal{A}\left(V\right)=\mathit{AV}+\Phi \left(V\right)-G$ est une M-fonction continue surjective, c’est-à-dire hors diagonale décroissante et $\mathcal{A}\left(V\right)$ inverse monotone, i.e. $\mathcal{A}\left(V\right)\le \mathcal{A}\left(U\right)$ entraîne V ≤ U, et de plus $\mathcal{A}\left(V\right)$ est supposée continue et surjective ;

• les itérés successifs U^r appartiennent à des ensembles emboités ${\mathbb{E}}^r$ centrés en U* .

Dans la mesure où dans la suite, on aura à utiliser l’un de ces résultats, on rappelle les critères présentés précédemment dans le premier article [AF 1 385] dans la section 1 suivante.