Thèse de doctorat : Informatique : Metz : 2007. / Thèse soutenue sur ensemble de travaux. Bibliogr. p. [177]-194. Index p. [189]-192. Liste des symboles p. [193]-194.

Thèse de doctorat : SCIENCES APPLIQUEES : Metz : 1998. / 1998METZ011S. 129 REF.

Dans ma thèse, je présente un nouveau schéma aux différences d'ordre 4 pour le problème de Poisson dans un carré et dans un cube avec conditions limites de Dirichlet. Ce schéma généralise l'approche donnée par Croisille en Compting 2006. La conception du schéma est basée sur une formulation mixte combinant l'approximation de gradient par une dérivée hermitienne d'ordre 4 avec une formulation conservative discrète sur des boîtes de longueur 2h. L'étude comporte les deux aspects suivants.• Premièrement, montrer qu'une précision d'ordre 4 est obtenue pour les deux inconnues, la solution et son gradient.• Deuxièmement, donner un algorithme de résolution directe rapide basé sur la formule de Sherman-Morrison-Woodbury et la transformée en sinus rapide. Plusieurs résultats numériques montrent que la complexité algorithmique est en O(N^2 log_2 (N )) en dimension 2 et O(N^3 log_2 (N )) en dimension 3.De très bonnes performances de calcul ont été obtenues sur une machine de bureau. A titre d'exemple, un calcul sur un maillage 1024 × 1024 est effectué en moins de cinq secondes sur un PC ordinaire. Ce solveur sert de pré conditionnement des problèmes elliptiques non réguliers. Une autre application concerne les maillages cartésiens multiéchelle. Ce type de maillages permet une résolution locale également d'ordre 4 sur des zones raffinées. Le raffinement est récursif. Les schémas boîte sont actuellement de plus en plus étudiés. Ils sont étudiés par I. Greff en 2003 pour différents problèmes elliptiques avec les méthodes d'éléments finis. Ils ont été récemment étudié par J.B. Perot en 2007.Les perspectives principales de ce travail sont les suivantes :- Généralisation des schémas boîte sur une grille cartésienne à des problèmes avec obstacles.La méthode envisagée est de type “embedded boundary”.- Utilisation du schéma présenté pour des applications en physique des particules.L'opérateur de moyenne Π^0 f_{i,j} correspond à la charge électrique dans la boîte K_{i,j} . Le schéma sert dans ce cas à calculer le potentiel et le champ électromagnétique.- Utilisation du schéma pour des modèles complexes d'équations elliptiques, comme MEMS(Microelectromechanical Systems), travail récent des Prof. Ghoussoub, Ward, Lindsay, et des équations modélisant des streamers, projet actuel à CWI du Prof. Hundsdorfer / My work is devoted to both Applied Mathematics and Scientific Computing. Concerning Scientific Computing I worked on the design and implementation of efficient fast solvers which are a crucialissue to perform practical computations. The use of such solvers in canonical geometries is at theheart of many computing codes in physics. Examples are fluid dynamics (compressible or incom-pressible Navier-Stokes equations), the Helmholtz equation, problems in astrophysics or in geophysics.In my thesis entitled « Hermitian Box Scheme - Fast Algorithms to solve Partial Differential Equations » supervised by Prof. J.P. Croisille 1 , I have developed a new compact scheme called “Hermitian Box” scheme. The focus is on Cartesian or cubic geometries with an emphasis on the fast resolution procedure. It extends the approach given by Croisille in Computing 2006. The design is based on a “Hermitian Box” approach, combining approximations of the gradient and of a discrete form of the conservation equations of “boxes” of length 2h.The main properties of the new scheme is that it is fourth order accurate for the unknown u andits gradient ∇u and satisfy the maximum principles. The code that is developed so far treats the Poisson problem in one, two and three dimensions. This problem is still the bottleneck of many computing codes in physics such as particle/grids problems in electromagnetism, gravitation, ... etc.As a first example of the computing efficiency of the new scheme we give the results obtained sofar for the three-dimensional Poisson problem in a cube−∆u(x, y, z) = f (x, y, z), in Ω = ]0, 1[x]0,1[x]0,1[,u = g, on ∂Ω.In the numerical tables, we report the maximum errors for the “Hermitian Box” (HB) scheme with different grids. The numerical results show that the HB scheme achieves fourth order convergence rate for both u and ∇u. We compare the accuracy of our scheme with the five points Laplacian scheme (CDS). The scheme CDS achieves a second order convergence rate. We note that the HB scheme yields a solution which is more accurate than that by CDS. For example, to obtain a solution with maximum error 10−4 , CDS needs a mesh-size h = 1/64, but HB only needs a mesh-size h = 1/8. If this fact is translated into CPU time, we see that HB scheme is hundreds of times faster than CDS to provide a numerically calculated solution of same accuracy.Our scheme was also used for the discretization of non separable elliptic problems in two dimensions such as−div(a(x, y)∇u(x, y)) = f (x, y), in Ω =]a, b[×]c, d[,u = g, on ∂Ω.Where a(x,y) is a regular function satisfying 0 < a(x, y) for (x, y) ∈ Ω.Meanwhile, due to the high accuracy on the boundary, the HB scheme was found very accurate when coupled to a Local Defect Correction technique in cases where the solution has a steep gradient in a small domain Ω_l

Thesis--Linköpings universitet, 2000. / Notes bibliogr.

Reproduction de : Thèse de 3e cycle : informatique : Grenoble, INPG : 1983. / Titre provenant de l'écran-titre. Bibliogr. p. 153-164.

Thèse (M.Sc.)--Université Laval, 2005. / Titre de l'écran-titre (visionné le 15 décembre 2005). Bibliogr.

Th. 3e cycle--Math.--Besançon, 1983. N°: 423.

Th. 3e cycle--Math.--Besançon, 1981. N°: 375.

Th.--Informatique et réseaux--Paris--ENST, 1993. / Bibliogr. p. 186-194.

Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leurdéploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers. / Real-world optimization problems are often complex and NP-hard. Their modeling is continuously evolving in terms of constraints and objectives, and their resolution is CPU time-consuming. Although near-optimal algorithms such as metaheuristics (generic heuristics) make it possible to reduce the temporal complexity of their resolution, they fail to tackle large problems satisfactorily. Over the last decades, parallel computing has been revealed as an unavoidable way to deal with large problem instances of difficult optimization problems. The design and implementation of parallel metaheuristics are strongly influenced by the computing platform. Nowadays, GPU computing has recently been revealed effective to deal with time-intensive problems. This new emerging technology is believed to be extremely useful to speed up many complex algorithms. One of the major issues for metaheuristics is to rethink existing parallel models and programming paradigms to allow their deployment on GPU accelerators. Generally speaking, the major issues we have to deal with are: the distribution of data processing between CPU and GPU, the thread synchronization, the optimization of data transfer between the different memories, the memory capacity constraints, etc. The contribution of this thesis is to deal with such issues for the redesign of parallel models of metaheuristics to allow solving of large scale optimization problems on GPU architectures. Our objective is to rethink the existing parallel models and to enable their deployment on GPUs. Thereby, we propose in this document a new generic guideline for building efficient parallel metaheuristics on GPU. Our challenge is to come out with the GPU-based design of the whole hierarchy of parallel models.In this purpose, very efficient approaches are proposed for CPU-GPU data transfer optimization, thread control, mapping of solutions to GPU threadsor memory management. These approaches have been exhaustively experimented using five optimization problems and four GPU configurations. Compared to a CPU-based execution, experiments report up to 80-fold acceleration for large combinatorial problems and up to 2000-fold speed-up for a continuous problem. The different works related to this thesis have been accepted in a dozen of publications, including the IEEE Transactions on Computers journal.