Catégories
Algorithme

Algorithme

algorithme

Définition

Un algorithme est une suite finie et non ambiguë d’opérations ou d’instructions permettant de résoudre une classe de problèmes. Le mot algorithme vient du nom d’un mathématicien perse du IXe siècle, Al-Khwârizmî (en arabe : الخوارزمي). Le domaine qui étudie les algorithmes est appelé l’algorithmique. On retrouve aujourd’hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs3, la cryptographie, le routage d’informations, la planification et l’utilisation optimale des ressources, le traitement d’images, le traitement de textes, la bio-informatique, etc.

Algorithmes en traitement d’images

Les algorithmes les plus récents de traitement numérique de la géométrie ou bien encore de simulation numérique de type CFD (Computational Fluid Dynamics) utilisent à présent de nouveaux types de grilles composées de polyèdres arbitraires, autrement dit des grilles fortement non-structurées. Dans le cas de simulations de type CFD, ces grilles peuvent servir de support à des champs scalaires ou vectoriels qui représentent des grandeurs physiques (par exemple : densité, porosité, perméabilité).

La problématique de cette thèse concerne la définition de nouveaux outils de visualisation et de calcul sur de telles grilles. Pour la visualisation, cela pose à la fois le problème du stockage et de l’adaptativité des algorithmes à une géométrie et une topologie variables. Pour le calcul, cela pose le problème de la résolution de grands systèmes linéaires creux non-structurés. Pour aborder ces problèmes, l’augmentation incessante ces dernières années de la puissance de calcul parallèle des processeurs graphiques nous fournit de nouveaux outils. Toutefois, l’utilisation de ces GPU nécessite de définir de nouveaux algorithmes adaptés aux modèles de programmation parallèle qui leur sont spécifiques.

Nos contributions sont les suivantes : (1) Une méthode générique de visualisation tirant partie de la puissance de calcul des GPU pour extraire des isosurfaces à partir de grandes grilles fortement non structurées. (2) Une méthode de classification de cellules qui permet d’accélérer l’extraction d’isosurfaces grâce à une présélection des seules cellules intersectées. (3) Un algorithme d’interpolation temporelle d’isosurfaces. Celui-ci permet de visualiser de manière continue dans le temps l’évolution d’isosurfaces. (4) Un algorithme massivement parallèle de résolution de grands systèmes linéaires non-structurés creux sur le GPU. L’originalité de celui-ci concerne son adaptation à des matrices de motif arbitraire, ce qui le rend applicable à n’importe quel système creux, dont ceux issus de maillages fortement non-structurés.

Cours PDF

Autres cours

Tout les cours

Laisser un commentaire