The central theme of this thesis is the design of optimal balanced black-box stopping criteria in iterative solvers of symmetric positive-definite, symmetric indefinite, and nonsymmetric linear systems arising from finite element approximation of stochastic (parametric) partial differential equations. For a given stochastic and spatial approximation, it is known that iteratively solving the corresponding linear(ized) system(s) of equations to too tight algebraic error tolerance results in a wastage of computational resources without decreasing the usually unknown approximation error. In order to stop optimally-by avoiding unnecessary computations and premature stopping-algebraic error and a posteriori approximation error estimate must be balanced at the optimal stopping iteration. Efficient and reliable a posteriori error estimators do exist for close estimation of the approximation error in a finite element setting. But the algebraic error is generally unknown since the exact algebraic solution is not usually available. Obtaining tractable upper and lower bounds on the algebraic error in terms of a readily computable and monotonically decreasing quantity (if any) of the chosen iterative solver is the distinctive feature of the designed optimal balanced stopping strategy. Moreover, this work states the exact constants, that is, there are no user-defined parameters in the optimal balanced stopping tests. Hence, an iterative solver incorporating the optimal balanced stopping methodology that is presented here will be a black-box iterative solver. Typically, employing such a stopping methodology would lead to huge computational savings and in any case would definitely rule out premature stopping. The constants in the devised optimal balanced black-box stopping tests in MINRES solver for solving symmetric positive-definite and symmetric indefinite linear systems can be estimated cheaply on-the- fly. The contribution of this thesis goes one step further for the nonsymmetric case in the sense that it not only provides an optimal balanced black-box stopping test in a memory-expensive Krylov solver like GMRES but it also presents an optimal balanced black-box stopping test in memory-inexpensive Krylov solvers such as BICGSTAB(L), TFQMR etc. Currently, little convergence theory exists for the memory-inexpensive Krylov solvers and hence devising stopping criteria for them is an active field of research. Also, an optimal balanced black-box stopping criterion is proposed for nonlinear (Picard or Newton) iterative method that is used for solving the finite dimensional Navier-Stokes equations. The optimal balanced black-box stopping methodology presented in this thesis can be generalized for any iterative solver of a linear(ized) system arising from numerical approximation of a partial differential equation. The only prerequisites for this purpose are the existence of a cheap and tight a posteriori error estimator for the approximation error along with cheap and tractable bounds on the algebraic error.

Le point de départ de cette thèse est un problème posé par le groupe électromagnétisme de EADS-CCR : comment résoudre plusieurs systèmes linéaires avec la même matrice mais différents seconds membres ? Pour l'application voulue, les matrices sont complexes, denses et de grande taille. Un problème standard comporte environ quelques millions d'inconnues. Comme de telles matrices ne peuvent être ni calculées, ni stockées dans un processus industriel, l'utilisation d'un produit matrice-vecteur approché est la seule alternative. En l'occurrence, le produit matrice-vecteur est effectué en utilisant la méthode multipôle rapide. Dans ce contexte, le but de cette thèse est d'adapter les méthodes itératives de type Krylov de telle sorte qu'elles traitent efficacement les nombreux seconds membres. Des travaux préliminaires avec un seul second membre ont montré que la méthode GMRES est particulièrement efficace et robuste pour cette application. En conséquence dans cette thèse nous abordons uniquement les variantes de GMRES. Les schémas d'orthogonalisation que nous avons implantés dans GMRES sont des variantes de l'algorithme de Gram-Schmidt. <br /><br />Dans une première partie, nous nous intéressons à l'influence des erreurs d'arrondi dans les algorithmes de Gram-Schmidt. Nos résultats répondent à des questions vieilles de vingt-cinq ans. Nous donnons l'explication théorique de ce qui était communément observé et accepté : <br /><br /> - l'algorithme de Gram-Schmidt modifié génère un ensemble de vecteurs bien conditionné ;<br /> - l'algorithme de Gram-Schmidt itéré deux fois fabrique un ensemble de vecteurs orthonormé.<br /><br />Ces deux propositions reposent sur l'hypothèse que la matrice de départ est "numériquement non singulière" en un sens qui est clairement défini. D'autre part, quand l'algorithme de Gram-Schmidt est itéré avec un critère de réorthogonalisation, nous proposons un nouveau critère. Nous montrons que l'algorithme obtenu est robuste alors que le critère communément utilisé est mis en défaut dans certains cas. Finalement, nous généralisons des résultats standards sur les normes en terme de valeurs singulières pour l'algorithme de Gram-Schmidt modifié. Ceci nous permet de dériver un schéma de réorthogonalisation a posteriori utilisant une matrice de rang faible. Ces résultats ont plusieurs applications directes. Nous en donnons des exemples avec les méthodes de Krylov pour résoudre des problèmes linéaires avec plusieurs seconds membres.<br /><br />Dans la deuxième partie, nous avons implémenté des variantes de la méthode GMRES pour les arithmétiques réelle et complexe, simple et double précisions. Cette implémentation convient pour des ordinateurs classiques, à mémoire partagée ou distribuée. Le code en résultant satisfait aux critères de qualité des librairies standards et son implémentation est largement détaillée. Pour des besoins de simplicité, flexibilité et efficacité, les solveurs utilisent un mécanisme de reverse communication pour les produits matrice-vecteur, les étapes de préconditionnement et les produits scalaires. Différents schémas d'orthogonalisation sont implémentés pour réduire le coût de calcul des produits scalaires, un point particulièrement important pour l'efficacité des méthodes de Krylov dans un environnement parallèle distribué. Le critère d'arrêt implémenté est basé sur l'erreur inverse normalisée. Les variantes disponibles sont GMRES-DR, seed-GMRES et block-GMRES. Ces codes s'ajoutent aux variantes déjà existantes (GMRES, flexible GMRES et SQMR). Un produit matrice-vecteur avec une décomposition LU est utilisé dans GMRES-DR de telle sorte que le stockage des approximations des vecteurs propres se fasse sur les premiers vecteurs de l'espace de Krylov. Un restart implicite et une étape de préconditionnement implicite ont été implémentés dans seed-GMRES. Nous supprimons ainsi un produit matrice-vecteur et une étape de préconditionnement par second membre et par cycle de GMRES. La version de block-GMRES permet à l'utilisateur de sélectionner différents modes de déflation. Pour terminer, des résultats reliant la norme du résidu de GMRES à la plus petite valeur singulière de l'espace construit par la méthode de Krylov ont été généralisés à la méthode block-GMRES.<br /><br />La troisième partie est consacrée à l'amélioration des techniques standards pour la résolution des systèmes linéaires dans le cadre des problèmes électromagnétiques. Après une présentation approfondie du code, nous étudions l'influence de la non-symétrie sur la convergence de l'algorithme SQMR. Nous étudions aussi le comportement de GMRES-DR sur nos problèmes. Ceci correspond à deux méthodes avec un seul second membre, le reste de cette partie concerne les cas comportant plusieurs seconds membres. Tout d'abord, nous examinons en détail les techniques qui permettent d'adapter les méthodes utilisées pour un second membre unique aux cas comportant plusieurs seconds membres. Par exemple, on peut améliorer la qualité du préconditionneur, avoir une stratégie de solution initiale, grouper les opérations de plusieurs résolutions ou encore paralléliser plusieurs résolutions. Dans le contexte du calcul de surface équivalente radar monostatique, nous avons montré que l'espace des seconds membres du problème continu était de dimension finie. La dimension donnée par notre théorie est proche de celle que nous observons en pratique. Cette propriété nous permet de réduire considérablement le nombre de systèmes linéaires à résoudre. Dans ce contexte, une version de la méthode block-GMRES est donnée. Ensuite, nous abordons certains problèmes spécifiques des méthodes seed-GMRES et block-GMRES pour lesquels nous proposons des solutions. Pour finir, des résultats plus prospectifs sont donnés. Plusieurs stratégies pour extraire et ajouter de l'information spectrale d'un cycle de GMRES à l'autre sont proposées et comparées. Puis nous utilisons le fait que la méthode multipôle rapide est un produit matrice-vecteur inexact dont la précision est réglable. Moins précis est le produit matrice-vecteur, plus rapide il est. Nous montrons comment tirer partie de cette propriété en utilisant un schéma relâché (méthode de Krylov inexacte) ou des itérations emboîtées (flexible GMRES). Enfin, le critère d'arrêt basé sur l'erreur inverse normalisée dans le cadre du calcul d'une surface équivalente radar est remis en question.

La prévention des risques industriels nécessite de simuler la dispersion turbulente de polluants. Cependant, les outils majoritairement utilisés à ce jour ne permettent pas de traiter les champs proches dans le cas de géométries complexes, et il est nécessaire d'utiliser les outils de CFD (“ Computational Fluid Dynamics ”) plus adaptés, mais plus coûteux. Afin de simuler les écoulements atmosphériques avec dispersion de polluants, les modèles CFD doivent modéliser correctement d'une part, les effets de flottabilité, et d'autre part les effets de la turbulence. Plusieurs approches existent, notamment dans la prise en compte des effets de flottabilité et la modélisation de la turbulence, et nécessitent des méthodes numériques adaptées aux spécificités mathématiques de chacune d'entre elles, ainsi que des schémas numériques précis pour ne pas polluer la modélisation. Une formulation d'ordre élevé en volumes finis, sur maillages non structurés, parallélisée, est proposée pour simuler les écoulements atmosphériques avec dispersion de polluants. L'utilisation de schémas d'ordre élevé doit permettre d'une part de réduire le nombre de cellules et diminuer les temps de simulation pour atteindre une précision donnée, et d'autre part de mieux contrôler la viscosité numérique des schémas en vue de simulations LES (Large Eddy Simulation), pour lesquelles la viscosité numérique des schémas peut masquer les effets de la modélisation. Deux schémas d'ordre élevé ont été étudiés et implémentés dans un solveur 3D Navier Stokes incompressible sur des maillages volumes finis non structurés. Nous avons développé un premier schéma d'ordre élevé, correspondant à un schéma Padé volumes finis, et nous avons étendu le schéma de reconstruction polynomiale de Carpentier (2000) aux écoulements incompressibles. Les propriétés numériques des différents schémas implémentés dans le même code de calcul sont étudiées sur différents cas tests bi-dimensionnels (calcul de flux convectifs et diffusifs sur une solution a-priori, convection d'une tâche gaussienne, décroissance d'un vortex de Taylor et cavité entraînée) et tri-dimensionnel (écoulement autour d'un obstacle cubique). Une attention particulière a été portée à l'étude de la précision et du traitement des conditions limites. L'implémentation proposée du schéma polynomial permet d'approcher, pour un maillage identique, les temps de simulation obtenus avec un schéma décentré classique d'ordre 2, mais avec une précision supérieure. Le schéma compact donne la meilleure précision. En utilisant une méthode de Jacobi sans calcul implicite de la matrice pour calculer le gradient, le temps de simulation devient intéressant uniquement lorsque la précision requise est importante. Une alternative est la résolution du système linéaire par une méthode multigrille algébrique. Cette méthode diminue considérablement le temps de calcul du gradient et le schéma Padé devient performant même pour des maillages grossiers. Enfin, pour réduire les temps de simulation, la parallélisation des schémas d'ordre élevé est réalisée par une décomposition en sous domaines. L'assemblage des flux s'effectue naturellement et différents solveurs proposés par les librairies PETSC et HYPRE (solveur multigrille algébrique et méthode de Krylov préconditionnée) permettent de résoudre les systèmes linéaires issus de notre problème. Le travail réalisé a consisté à identifier et déterminer les paramètres de résolution qui conduisent aux temps de simulation les plus faibles. Différents tests de speed-up et de scale-up ont permis de déterminer la méthode la plus efficace et ses paramètres optimaux pour la résolution en parallèle des systèmes linéaires issus de notre problème. Les résultats de ce travail ont fait l'objet d'une communication dans un congrès international “ parallel CFD juin 2008 ” et d'un article soumis à “ International Journal for Numerical Methods in Fluids ” (Analysis of high-order finite volume schemes for the incompressible Navier Stokes equations)

La résolution des équations de Navier-Stokes linéarisées compressibles est utilisée pour 2 types de problèmes : 1. Pour la résolution de problèmes d'aéroélastcité et d'aéroacoutstique 2. Les exercices d'optimisation par méthode du gradient Les algorithmes proposés sont généralement basés sur une approche dite time-marching simplifiant le développement numérique. Dans ce doctorat nous avons développer une méthode sans intégration temporelle pour stabiliser la résolution des équations de Navier-Stokes linéarisées. Les systèmes linéaires obtenus sont résolus par une méthode itérative de type GMRes-ILU0. Les résultats numériques sont comparés à une approche AF-ADI et GMRes-time-marching pour des calculs 2D relatif à une perturbation harmonique de pression. La méthode de résolution est aussi validée pour 2 exercices d'optimisation. Une méthode de résolution pseudo-Newton-GMRes des équations de Navier-Stokes non linéaires faiblement couplée a aussi été validée dans le cas d'écoulements 2D.

Cette thèse porte sur des méthode de résolution d'équations matricielles appliquées à la résolution numérique d'équations aux dérivées partielles ou des problèmes de contrôle linéaire. On s'intéressen en premier lieu à des équations matricielles linéaires. Après avoir donné un aperçu des méthodes classiques employées pour les équations de Sylvester et de Lyapunov, on s'intéresse au cas d'équations linéaires générales de la forme M(X)=C, où M est un opérateur linéaire matriciel. On expose la méthode de GMRES globale qui s'avère particulièrement utile dans le cas où M(X) ne peut s'exprimer comme un polynôme du premier degré en X à coefficients matriciels, ce qui est le cas dans certains problèmes de résolution numérique d'équations aux dérivées partielles. Nous proposons une approche, noté LR-BA-ADI consistant à utiliser un préconditionnement de type ADI qui transforme l'équation de Sylvester en une équation de Stein que nous résolvons par une méthode de Krylox par blocs. Enfin, nous proposons une méthode de type Newton-Krylov par blocs avec préconditionnement ADI pour les équations de Riccati issues de problèmes de contrôle linéaire quadratique. Cette méthode est dérivée de la méthode LR-BA-ADI. Des résultats de convergence et de majoration de l'erreur sont donnés. Dans la seconde partie de ce travail, nous appliquons les méthodes exposées dans la première partie de ce travail à des problèmes d'équations aux dérivées partielles. Nous nous intéressons d'abord à la résolution numérique d'équations couplées de type Burgers évolutives en dimension 2. Ensuite, nous nous intéressons au cas où le domaine borné est choisi quelconque. Nous établissons des résultats théoriques de l'existence de tels interpolants faisant appel à des techniques d'algèbre linéaire.

La prévention des risques industriels nécessite de simuler la dispersion turbulente de polluants. Cependant, les outils majoritairement utilisés à ce jour ne permettent pas de traiter les champs proches dans le cas de géométries complexes, et il est nécessaire d'utiliser les outils de CFD (" Computational Fluid Dynamics ") plus adaptés, mais plus coûteux. Afin de simuler les écoulements atmosphériques avec dispersion de polluants, les modèles CFD doivent modéliser correctement d'une part, les effets de flottabilité, et d'autre part les effets de la turbulence. Plusieurs approches existent, notamment dans la prise en compte des effets de flottabilité et la modélisation de la turbulence, et nécessitent des méthodes numériques adaptées aux spécificités mathématiques de chacune d'entre elles, ainsi que des schémas numériques précis pour ne pas polluer la modélisation. Une formulation d'ordre élevé en volumes finis, sur maillages non structurés, parallélisée, est proposée pour simuler les écoulements atmosphériques avec dispersion de polluants. L'utilisation de schémas d'ordre élevé doit permettre d'une part de réduire le nombre de cellules et diminuer les temps de simulation pour atteindre une précision donnée, et d'autre part de mieux contrôler la viscosité numérique des schémas en vue de simulations LES (Large Eddy Simulation), pour lesquelles la viscosité numérique des schémas peut masquer les effets de la modélisation. Deux schémas d'ordre élevé ont été étudiés et implémentés dans un solveur 3D Navier Stokes incompressible sur des maillages volumes finis non structurés. Nous avons développé un premier schéma d'ordre élevé, correspondant à un schéma Padé volumes finis, et nous avons étendu le schéma de reconstruction polynomiale de Carpentier (2000) aux écoulements incompressibles. Les propriétés numériques des différents schémas implémentés dans le même code de calcul sont étudiées sur différents cas tests bi-dimensionnels (calcul de flux convectifs et diffusifs sur une solution a-priori, convection d'une tâche gaussienne, décroissance d'un vortex de Taylor et cavité entraînée) et tri-dimensionnel (écoulement autour d'un obstacle cubique). Une attention particulière a été portée à l'étude de la précision et du traitement des conditions limites. L'implémentation proposée du schéma polynomial permet d'approcher, pour un maillage identique, les temps de simulation obtenus avec un schéma décentré classique d'ordre 2, mais avec une précision supérieure. Le schéma compact donne la meilleure précision. En utilisant une méthode de Jacobi sans calcul implicite de la matrice pour calculer le gradient, le temps de simulation devient intéressant uniquement lorsque la précision requise est importante. Une alternative est la résolution du système linéaire par une méthode multigrille algébrique. Cette méthode diminue considérablement le temps de calcul du gradient et le schéma Padé devient performant même pour des maillages grossiers. Enfin, pour réduire les temps de simulation, la parallélisation des schémas d'ordre élevé est réalisée par une décomposition en sous domaines. L'assemblage des flux s'effectue naturellement et différents solveurs proposés par les librairies PETSC et HYPRE (solveur multigrille algébrique et méthode de Krylov préconditionnée) permettent de résoudre les systèmes linéaires issus de notre problème.

Advances in numerical optimization have raised the possibility that efficient and novel aircraft configurations may be ``discovered'' by an algorithm. To begin exploring this possibility, a fast and robust set of tools for aerodynamic shape optimization is developed. Parameterization and mesh-movement are integrated to accommodate large changes in the geometry. This integrated approach uses a coarse B-spline control grid to represent the geometry and move the computational mesh; consequently, the mesh-movement algorithm is two to three orders faster than a node-based linear elasticity approach, without compromising mesh quality. Aerodynamic analysis is performed using a flow solver for the Euler equations. The governing equations are discretized using summation-by-parts finite-difference operators and simultaneous approximation terms, which permit nonsmooth mesh continuity at block interfaces. The discretization results in a set of nonlinear algebraic equations, which are solved using an efficient parallel Newton-Krylov-Schur strategy. A gradient-based optimization algorithm is adopted. The gradient is evaluated using adjoint variables for the flow and mesh equations in a sequential approach. The flow adjoint equations are solved using a novel variant of the Krylov solver GCROT. This variant of GCROT is flexible to take advantage of non-stationary preconditioners and is shown to outperform restarted flexible GMRES. The aerodynamic optimizer is applied to several studies of induced-drag minimization. An elliptical lift distribution is recovered by varying spanwise twist, thereby validating the algorithm. Planform optimization based on the Euler equations produces a nonelliptical lift distribution, in contrast with the predictions of lifting-line theory. A study of spanwise vertical shape optimization confirms that a winglet-up configuration is more efficient than a winglet-down configuration. A split-tip geometry is used to explore nonlinear wake-wing interactions: the optimized split-tip demonstrates a significant reduction in induced drag relative to a single-tip wing. Finally, the optimal spanwise loading for a box-wing configuration is investigated.

No description available.

A new method for the determination of finely-gridded reservoir simulation pressures has been developed. It is estimated to be as much as hundreds to thousands of times faster than other methods for very large reservoir simulation grids. The method extends the work of Weber et al. Weber demonstrated accuracies for the pressure solution normally requiring millions of cells using traditional finite-difference equations with only hundreds of cells. This was accomplished through the use of finite-difference equations that incorporate the physics of the flow. Although these coarse-grid solutions achieve accuracies normally requiring orders of magnitude more resolution, their coarse resolution does not resolve local pressure variations resulting from fine-grid permeability variations. Many oil reservoir simulation models require fine grids to adequately represent the reservoir properties. Weber's coarse grids are of little value. This study takes advantage of the accurate coarse-grid solutions of Weber, by nesting them in the requisite fine grids to achieve much faster solutions of the large systems. Application of the nested-grid method involved calculating an accurate solution on a coarse grid, nesting the coarse-grid solution as fixed points into a finer grid and solving. Best results were obtained when an optimal number of coarse-grid pressure points were nested into the fine grid and when an optimal number of nested-grid systems were used.

La résolution de très grands systèmes linéaires creux est une composante de base algorithmique fondamentale dans de nombreuses applications scientifiques en calcul intensif. La résolution per- formante de ces systèmes passe par la conception, le développement et l'utilisation d'algorithmes parallèles performants. Dans nos travaux, nous nous intéressons au développement et l'évaluation d'une méthode hybride (directe/itérative) basée sur des techniques de décomposition de domaine sans recouvrement. La stratégie de développement est axée sur l'utilisation des machines mas- sivement parallèles à plusieurs milliers de processeurs. L'étude systématique de l'extensibilité et l'efficacité parallèle de différents préconditionneurs algébriques est réalisée aussi bien d'un point de vue informatique que numérique. Nous avons comparé leurs performances sur des systèmes de plusieurs millions ou dizaines de millions d'inconnues pour des problèmes réels 3D .