Annexe : compléments théoriques pour l’analyse en contraction
Algorithmes parallèles asynchrones III - Application, performances

Dans un premier article [AF 1 385], pour résoudre des problèmes pseudo-linéaires univoques et multivoques, ce dernier cas correspondant à la situation où la solution est soumise à des contraintes de type inégalité, nous avons présenté le modèle mathématique décrivant les méthodes itératives parallèles asynchrones. Nous avons également présenté trois méthodes distinctes permettant, sous des hypothèses convenables, d’analyser le comportement de ces méthodes itératives. L’analyse de la convergence de ces méthodes peut s’effectuer soit par des techniques de contraction, soit par des techniques d’ordre partiel liées à l’utilisation du principe du maximum discret, soit encore parce que les itérés successifs appartiennent à des ensembles emboités centrés sur la solution U^* du problème à résoudre. Il est à noter que cette dernière approche reposant sur les ensembles emboités permet d’unifier les deux approches précédentes basées sur des techniques de contraction ou d’ordre partiel mais cependant ne fournit pas de critères pratiques de convergence. Une comparaison de ces trois techniques d’analyse a permis de dégager les avantages de chacune d’elle ; en particulier, sous des hypothèses convenables, les techniques de contraction permettent de donner une estimation de la vitesse asymptotique de convergence de ces méthodes itératives et d’obtenir une propriété de convergence quelle que soit la décomposition en blocs du problème à résoudre. De plus ce type d’analyse par contraction est utilisable pour la résolution de problèmes pseudo-linéaires univoques et multivoques, alors que les techniques d’ordre partiel ne peuvent être utilisables que pour la résolution de problèmes pseudo-linéaires univoques dans la mesure où l’hypothèse de continuité nécessaire dans le critère d’analyse par des techniques d’ordre partiel n’est pas satisfaite.

Toujours dans ce premier article [AF 1 385], il a été indiqué diverses méthodes de décomposition en blocs du problème à résoudre. Il s’agit des méthodes de sous-domaines ou plus généralement des méthodes de multi-décomposition. Grâce aux résultats établis précédemment l’analyse du comportement de ces méthodes a pu être étudiée. Enfin dans cet article divers exemples de problèmes classiques, où les critères d’analyse ont été appliqués pratiquement, ont été présentés.

L’article suivant [AF 1 386], consacré à l’implémentation des méthodes itératives parallèles asynchrones comporte deux parties distinctes nécessaires à la mise en oeuvre de ces méthodes. La première partie est consacrée à la terminaison de ces algorithmes itératifs parallèles asynchrones ; c’est un problème très difficile qui nécessite l’utilisation combinée de techniques informatiques diverses et variées ainsi que la mise en œuvre de tests numériques reposant soit sur les techniques de contraction, soit sur les techniques d’ordre partiel, soit sur les propriétés induites par l’analyse utilisant les ensembles emboités. Divers critères pratiques de terminaison ont été exposés. La seconde partie du deuxième article [AF 1 386] était consacrée à la mise en œuvre des algorithmes itératifs parallèles asynchrones sur des machines multiprocesseurs. Cette implémentation nécessite un rappel des concepts de programmation des algorithmes numériques ainsi que l’exposé d’une classification des architectures des machines multiprocesseurs et des diverses méthodes de parallélisation. Après avoir rappelé les concepts de base des fonctions MPI (Message Passing Interface), en particulier des mécanismes de communications synchrones et asynchrones, le principe d’implémentation des méthodes itératives parallèles asynchrones a été présenté. Divers aspects d’équilibrage des charges en algorithmique asynchrone ont également été décrits ainsi que l’utilisation des architectures GPU (Graphics Processing Unit).

Le présent article a pour vocation de compléter les deux précédents articles. Dans une première partie nous verrons diverses applications des algorithmes itératifs parallèles asynchrones pour, d’une part, résoudre numériquement des problèmes de grande dimension et, d’autre part, des problèmes non numériques en relation avec du calcul booléen ou des problèmes de sécurité informatique. Enfin, pour terminer nous analysons sur des exemples de problèmes réels et en fonction des architectures des machines, l’efficacité des algorithmes itératifs parallèles asynchrones comparée aux méthodes synchrones. On termine cette série d’articles par une annexe mathématique explicitant le plus simplement possible les concepts théoriques sous-jacents pour l’analyse de la convergence par contraction.