La pratique clinique a été profondément transformée par l'explosion technologique, ces dernières décades, des techniques d'imagerie médicale. L'expansion de la radiologie interventionnelle a ainsi rendu possible des procédures dites « minimalement invasives » au cours desquelles la thérapie est délivrée directement au niveau de la région pathologique via des micro-outils guidés par imagerie à travers le système vasculaire. Des systèmes dits « C-arm », générant une imagerie rayons X planaire temps-réelle en faible dose, sont utilisés pour le guidage. Ils ont offert plus récemment la possibilité d'une visualisation tridimensionnelle par le biais d'acquisitions tomographiques. C'est dans ce contexte de reconstruction tomographique que s'inscrivent ces travaux de thèse. Ils s'attèlent en particulier à corriger les artefacts de mouvement dus aux variations temporelles des vaisseaux injectés et se concentrent sur un aspect central de la tomographie, à savoir l'échantillonnage angulaire. La théorie du compressed sensing identifie les conditions sous lesquelles des données sous-échantillonnées peuvent être reconstruites en minimisant une fonctionnelle qui combine un terme de fidélité quadratique et une contrainte parcimonieuse. S'appuyant sur cette théorie, un formalisme original de reconstruction est proposé : il repose sur la rétroprojection filtrée itérative, les algorithmes proximaux, la minimisation de normes L1 et l'homotopie. Ce formalisme est ensuite dérivé pour intégrer différentes contraintes spatiales et temporelles. Une telle stratégie s'avère plus performante que la rétroprojection filtrée analytique utilisée dans la pratique clinique, permettant la réduction d'artefacts de mouvement et d'échantillonnage dans des cas cliniques bien identifiés de l'imagerie cérébrale et abdominale. Les résultats obtenus soulignent l'une des principales contributions de ce travail, à savoir : l'importance de l'homotopie, en supplément de la régularisation, pour améliorer la qualité image, un gain indispensable dans le domaine d'applicabilité / Medical imaging has known great advances over the past decades to become a powerful tool for the clinical practice. It has led to the tremendous growth of interventional radiology, in which medical devices are inserted and manipulated under image guidance through the vascular system to the pathology location and then used to deliver the therapy. In these minimally-invasive procedures, X-ray guidance is carried out with C-arm systems through two-dimensional real-time projective low-dose images. More recently, three-dimensional visualization via tomographic acquisition has also become available. This work tackles tomographic reconstruction in the aforementioned context. More specifically, it deals with the correction of motion artifacts that originate from the temporal variations of the contrast-enhanced vessels and thus tackles a central aspect of tomography: data (angular) sampling. The compressed sensing theory identifies conditions under which subsampled data can be recovered through the minimization of a least-square data fidelity term combined with sparse constraints. Relying on this theory, an original reconstruction framework is proposed based on iterative filtered backprojection, proximal splitting, `1-minimization and homotopy. This framework is derived for integrating several spatial and temporal penalties. Such a strategy is shown to outperform the analytical filtered backprojection algorithm that is used in the current clinical practice by reducing motion and sampling artifacts in well-identified clinical cases, with focus on cerebral and abdominal imaging. The obtained results emphasize one of the key contributions of this work that is the importance of homotopy in addition to regularization, to provide much needed image quality improvement in the suggested domain of applicability.

.

.

Depuis quelques années, les grappes équipées de processeurs graphiques GPUs sont devenues des outils très attrayants pour le calcul parallèle haute performance. Dans cette thèse, nous avons conçu des algorithmes itératifs parallèles pour la résolution de systèmes linéaires et non linéaires creux de très grandes tailles sur grappes de GPUs. Dans un premier temps, nous nous sommes focalisés sur la résolution de systèmes linéaires creux à l'aide des méthodes itératives CG et GMRES. Les expérimentations ont montré qu'une grappe de GPUs est plus performante que son homologue grappe de CPUs pour la résolution de systèmes linéaires de très grandes tailles. Ensuite, nous avons mis en oeuvre des algorithmes parallèles synchrones et asynchrones des méthodes itératives Richardson et de relaxation par blocs pour la résolution de systèmes non linéaires creux. Nous avons constaté que les meilleurs solutions développées pour les CPUs ne sont pas nécessairement bien adaptées aux GPUs. En effet, les simulations effectuées sur une grappe de GPUs ont montré que les algorithmes Richardson sont largement plus efficaces que ceux de relaxation par blocs. De plus, elles ont aussi montré que la puissance de calcul des GPUs permet de réduire le rapport entre le temps d'exécution et celui de communication, ce qui favorise l'utilisation des algorithmes asynchrones sur des grappes de GPUs. Enfin, nous nous sommes intéressés aux grappes géographiquement distantes pour la résolution de systèmes linéaires creux. Dans ce contexte, nous avons utilisé la méthode de multi-décomposition à deux niveaux avec GMRES parallèle adaptée aux grappes de GPUs. Celle-ci utilise des itérations synchrones pour résoudre localement les sous-systèmes linéaires et des itérations asynchrones pour résoudre la globalité du système linéaire.

Cette thèse propose des techniques numériques visant à optimiser les méthodes itératives d'évaluation de performances de modèles Markoviens. Ces techniques s'appliquent à des modèles où la matrice de transition de la chaîne de Markov associée est stockée sous un format tensoriel. Particulièrement, le formalisme des réseaux d'automates stochastiques est employé pour la description des modèles. L'évaluation de performances cherchée est la détermination de l'état stationnaire de la chaîne de Markov (\emph(résolution)). De ce fait, les propriétés de l'algèbre tensorielle généralisée sont proposées et démontrées de façon à établir la base nécessaire aux algorithmes de résolution introduits. Le principal apport de cette thèse réside dans l'efficacité des ces algorithmes, qui est obtenue avec l'accélération des méthodes itératives. Ceci est fait à deux niveaux: la réduction du coût de chaque itération; et la réduction du nombre d'itérations nécessaire à la convergence. La multiplication d'un vecteur par une matrice sous format tensoriel (produit vecteur-descripteur) est l'opération de base des itérations. L'efficacité de cette opération est le premier objectif à atteindre. Le deuxième objectif est l'implémentation des méthodes de la puissance, d'Arnoldi et GMRES dans ses versions standards et pré-conditionnées de façon a minimiser le nombre d'itérations sans trop augmenter le coût de chaque itération. La totalité des concepts introduits est alors utilisée dans le logiciel PEPS 2.0. Plusieurs exemples pratiques de modèles en réseaux d'automates stochastiques ont été mesurés sur PEPS 2.0 pour illustrer les résultats de cette thèse.

Ce travail est divisé en deux axes de recherches. Le premier axe concerne l'étude de quelques systèmes d'équations aux dérivées partielles non linéaires issus de la modélisation macroscopique des composants semi-conducteurs. Le deuxième axe de recherche est consacré à l'étude de quelques problèmes d'identification. Nous nous intéressons en particulier à deux types de problèmes d'identification. Le premier concerne la reconstruction des données sur le bord pour des problèmes elliptiques. Le deuxième type de problèmes auquel nous nous sommes intéressés est celui de l'identification des frontières dans des problèmes gouvernés par des équations elliptiques.

Dans cette thèse nous nous intéressons aux structures des algèbres quotients et plus particulièrement à l'apport de la dualité pour la représentation des algèbres de coordonnées. Une première partie de cette thèse est consacrée à la représentation des algèbres de dimension zéro et à des applications de la dualité à des problèmes d'interpolation. Nous généralisons les bases d'interpolation de Lagrange et d'Hermite pour lesquelles nous donnons des formules explicites. Cela nous permet de donner les relations entre les racines d'un système algébrique et ses coefficients avec des formules généralisant celles du cas univarié. Dans une deuxième partie, nous appliquons les résultats développés dans la première partie à la conception de méthodes itératives pour l'approximation simultanée de l'ensemble des solutions d'un système algébrique. La troisième partie est consacrée aux résidus algébriques. Nous rappelons les notions relatives aux algèbres de Gorenstein et à leurs représentations. Nous introduisons les bézoutiens et les résidus algébriques dont nous donnons des applications en géométrie. Dans la quatrième partie, nous nous intéressons à l'algorithmique associé aux matrices quasi-Toeplitz, quasi-Hankel, ..., telles que définies par B. Mourrain et V.Y. Pan. Nous en montrons des applications dans le cadre de l'algorithmique permettant des accélérations asymptotiques de méthodes de résolution de systèmes algébriques.

Les travaux de ce doctorat concernent le développement de méthodes itératives pour la résolution de systèmes linéaires creux de grande taille comportant de nombreux seconds membres. L’application visée est la résolution d’un problème inverse en géophysique visant à reconstruire la vitesse de propagation des ondes dans le sous-sol terrestre. Lorsque de nombreuses sources émettrices sont utilisées, ce problème inverse nécessite la résolution de systèmes linéaires complexes non symétriques non hermitiens comportant des milliers de seconds membres. Dans le cas tridimensionnel ces systèmes linéaires sont reconnus comme difficiles à résoudre plus particulièrement lorsque des fréquences élevées sont considérées. Le principal objectif de cette thèse est donc d’étendre les développements existants concernant les méthodes de Krylov par bloc. Nous étudions plus particulièrement les techniques de déflation dans le cas multiples seconds membres et recyclage de sous-espace dans le cas simple second membre. Des gains substantiels sont obtenus en terme de temps de calcul par rapport aux méthodes existantes sur des applications réalistes dans un environnement parallèle distribué. / This PhD thesis concerns the development of flexible Krylov subspace iterative solvers for the solution of large sparse linear systems of equations with multiple right-hand sides. Our target application is the solution of the acoustic full waveform inversion problem in geophysics associated with the phenomena of wave propagation through an heterogeneous model simulating the subsurface of Earth. When multiple wave sources are being used, this problem gives raise to large sparse complex non-Hermitian and nonsymmetric linear systems with thousands of right-hand sides. Specially in the three-dimensional case and at high frequencies, this problem is known to be difficult. The purpose of this thesis is to develop a flexible block Krylov iterative method which extends and improves techniques already available in the current literature to the multiple right-hand sides scenario. We exploit the relations between each right-hand side to accelerate the convergence of the overall iterative method. We study both block deflation and single right-hand side subspace recycling techniques obtaining substantial gains in terms of computational time when compared to other strategies published in the literature, on realistic applications performed in a parallel environment.

Depuis quelques années, les grappes équipées de processeurs graphiques GPUs sont devenues des outils très attrayants pour le calcul parallèle haute performance. Dans cette thèse, nous avons conçu des algorithmes itératifs parallèles pour la résolution de systèmes linéaires et non linéaires creux de très grandes tailles sur grappes de GPUs. Dans un premier temps, nous nous sommes focalisés sur la résolution de systèmes linéaires creux à l'aide des méthodes itératives CG et GMRES. Les expérimentations ont montré qu'une grappe de GPUs est plus performante que son homologue grappe de CPUs pour la résolution de systèmes linéaires de très grandes tailles. Ensuite, nous avons mis en oeuvre des algorithmes parallèles synchrones et asynchrones des méthodes itératives Richardson et de relaxation par blocs pour la résolution de systèmes non linéaires creux. Nous avons constaté que les meilleurs solutions développées pour les CPUs ne sont pas nécessairement bien adaptées aux GPUs. En effet, les simulations effectuées sur une grappe de GPUs ont montré que les algorithmes Richardson sont largement plus efficaces que ceux de relaxation par blocs. De plus, elles ont aussi montré que la puissance de calcul des GPUs permet de réduire le rapport entre le temps d'exécution et celui de communication, ce qui favorise l'utilisation des algorithmes asynchrones sur des grappes de GPUs. Enfin, nous nous sommes intéressés aux grappes géographiquement distantes pour la résolution de systèmes linéaires creux. Dans ce contexte, nous avons utilisé la méthode de multi-décomposition à deux niveaux avec GMRES parallèle adaptée aux grappes de GPUs. Celle-ci utilise des itérations synchrones pour résoudre localement les sous-systèmes linéaires et des itérations asynchrones pour résoudre la globalité du système linéaire. / Or the past few years, the clusters equipped with GPUs have become attractive tools for high performance computing. In this thesis, we have designed parallel iterative algorithms for solving large sparse linear and nonlinear systems on GPU clusters. First, we have focused on solving sparse linear systems using CG and GMRES iterative methods. The experiments have shown that a GPU cluster is more efficient that its pure CPU counterpart for solving large sparse systems of linear equations. Then, we have implemented the synchronous and asynchronous algorithms of the Richardson and the block relaxation iterative methods for solving sparse nonlinear systems. We have noticed that the best solutions developed for the CPUs are not necessarily well suited to GPUs. Indeed, the experiments performed on a GPU cluster have shown that the parallel algorithms of the Richardson method are far more efficient than those of the block relaxation method. In addition, they have shown that the computing power of GPUs allows to reduce the ratio between the time of the computation over that of the communication, which favors the use of the asynchronous iteration on GPU clusters. Finally, we are interested in geographically distant clusters for solving large sparse linear systems. In this context, we have used a multisplitting two-stage method using parallel GMRES method adapted to GPU clusters. It uses the synchronous iteration to solve locally the sub-linear systems and the asynchronous one to solve the global sparse linear system.

Avec l'avènement de machine parallèles multi-coeurs, de nombreux algorithmes doivent être modifiés ou conçus pour s'adapter à ces architectures. Ces algorithmes consistent pour la plupart à diviser le problème original en plusieurs petits sous-problèmes et à les distribuer sur les différentes unités de calcul disponibles. La résolution de ces petits sous-problèmes peut être exécutée en parallèle, des communications entre les unités de calcul étant indispensables pour assurer la convergence de ces méthodes.Ma thèse propose de nouveaux algorithmes parallèles pour résoudre de grands systèmes linéaires.Les algorithmes proposés sont ici basés sur la méthode du gradient. Deux points fondamentaux de la méthode du gradient sont la direction de descente de la solution approchée et la valeur du pas de descente, qui détermine la modification à effectuer à chaque itération. Nous proposons dans cette thèse de calculer la direction et le pas indépendamment et localement sur chaque unité de calcul, ce qui nécessite moins de synchronisation entre les processeurs, et par suite rend chaque itération simple et plus rapide, et rend son extension dans un contexte asynchrone possible.Avec les paramètres d'échelle appropriés pour le pas des longueurs, la convergence peut être démontrée pour les deux versions synchrone et asynchrone des algorithmes. De nombreux tests numériques illustrent l’efficacité de ces méthodes.L'autre partie de ma thèse propose d'utiliser une méthode d'extrapolation pour accélérer les méthodes itératives classiques avec retard. Bien que les séquences de vecteur générées par des méthodes itératives asynchrones générales classiques ne peut être accélérée, nous sommes en mesure de démontrer que, une fois le modèle de calcul et de communication fixés au cours de l’exécution, la séquence de vecteurs générés peut être accéléré. De nombreux tests numériques illustrent l’efficacité de ces accélérations dans le cas des méthodes avec retard. / With the increase of architectures composed of multi-cores, many algorithms need to revisited and be modified to exploit the power of these new architectures. These algorithms divide the original problem into “small pieces” and distribute these pieces to different processors at disposal, thus communications among them are indispensible to assure the convergence. My thesis mainly focus on solving large sparse systems of linear equations in parallel with new methods. These methods are based on the gradient methods. Two key parameters of the gradient methods are descent direction and step-length of descent for each iteration. Our methods compute the directions locally, which requires less synchronization and computation, leading to faster iterations and make easy asynchronization possible. Convergence can be proved in both synchronized or asynchronized cases. Numerical tests demonstrate the efficiency of these methods. The other part of my thesis deal with the acceleration of the vector sequences generated by classical iterative algorithms. Though general chaotic sequences may not be accelerated, it is possible to prove that with any fixed retard pattern, then the generated sequence can be accelerated. Different numerical tests demonstrate its efficiency.