A Newton-Krylov algorithm is presented for aerodynamic shape optimization in three dimensions using the Euler equations. An inexact-Newton method is used in the flow solver, a discrete-adjoint method to compute the gradient, and the quasi-Newton optimizer to find the optimum. A Krylov subspace method with approximate-Schur preconditioning is used to solve both the flow equation and the adjoint equation. Basis spline surfaces are used to parameterize the geometry, and a fast algebraic algorithm is used for grid movement. Accurate discrete-adjoint gradients can be obtained in approximately one-fourth the time required for a converged flow solution. Single- and multi-point lift-constrained drag minimization optimization cases are presented for wing design at transonic speeds. In all cases, the optimizer is able to efficiently decrease the objective function and gradient for problems with hundreds of design variables.

A Newton-Krylov algorithm is presented for aerodynamic shape optimization in three dimensions using the Euler equations. An inexact-Newton method is used in the flow solver, a discrete-adjoint method to compute the gradient, and the quasi-Newton optimizer to find the optimum. A Krylov subspace method with approximate-Schur preconditioning is used to solve both the flow equation and the adjoint equation. Basis spline surfaces are used to parameterize the geometry, and a fast algebraic algorithm is used for grid movement. Accurate discrete-adjoint gradients can be obtained in approximately one-fourth the time required for a converged flow solution. Single- and multi-point lift-constrained drag minimization optimization cases are presented for wing design at transonic speeds. In all cases, the optimizer is able to efficiently decrease the objective function and gradient for problems with hundreds of design variables.

A new parallel implicit adaptive mesh refinement (AMR) algorithm is developed for the prediction of unsteady behaviour of laminar flames. The scheme is applied to the solution of the system of partial-differential equations governing time-dependent, two- and three-dimensional, compressible laminar flows for reactive thermally perfect gaseous mixtures. A high-resolution finite-volume spatial discretization procedure is used to solve the conservation form of these equations on body-fitted multi-block hexahedral meshes. A local preconditioning technique is used to remove numerical stiffness and maintain solution accuracy for low-Mach-number, nearly incompressible flows. A flexible block-based octree data structure has been developed and is used to facilitate automatic solution-directed mesh adaptation according to physics-based refinement criteria. The data structure also enables an efficient and scalable parallel implementation via domain decomposition. The parallel implicit formulation makes use of a dual-time-stepping like approach with an implicit second-order backward discretization of the physical time, in which a Jacobian-free inexact Newton method with a preconditioned generalized minimal residual (GMRES) algorithm is used to solve the system of nonlinear algebraic equations arising from the temporal and spatial discretization procedures. An additive Schwarz global preconditioner is used in conjunction with block incomplete LU type local preconditioners for each sub-domain. The Schwarz preconditioning and block-based data structure readily allow efficient and scalable parallel implementations of the implicit AMR approach on distributed-memory multi-processor architectures. The scheme was applied to solutions of steady and unsteady laminar diffusion and premixed methane-air combustion and was found to accurately predict key flame characteristics. For a premixed flame under terrestrial gravity, the scheme accurately predicted the frequency of the natural buoyancy induced oscillations. The performance of the proposed parallel implicit algorithm was assessed by comparisons to more conventional solution procedures and was found to significantly reduce the computational time required to achieve a solution in all cases investigated.

La complexification de la modélisation multi-physique conduit d’une part à devoir simuler des systèmes d’équations différentielles ordinaires et d’équations différentielles algébriques de plus en plus grands en nombre d’inconnues et sur des temps de simulation longs. D’autre part l’évolution des architectures de calcul parallèle nécessite d’autres voies de parallélisation que la décomposition de système en sous-systèmes. Dans ce travail, nous proposons de concevoir des méthodes de décomposition de domaine pour la résolution d’EDO en temps. Nous reformulons le problème à valeur initiale en un problème aux valeurs frontières sur l’intervalle de temps symétrisé, sous l’hypothèse de réversibilité du flot. Nous développons deux méthodes, la première apparentée à une méthode de complément de Schur, la seconde basée sur une méthode de type Schwarz dont nous montrons la convergence pouvant être accélérée par la méthode d’Aitken dans le cadre linéaire. Afin d’accélérer la convergence de cette dernière dans le cadre non-linéaire, nous introduisons les techniques d’extrapolation et d’accélération de la convergence des suites non-linéaires. Nous montrons les avantages et les limites de ces techniques. Les résultats obtenus nous conduisent à développer l’accélération de la méthode de type Schwarz par une méthode de Newton. Enfin nous nous intéressons à l’étude de conditions de raccord non-linéaires adaptées à la décomposition de domaine de problèmes non-linéaires. Nous nous servons du formalisme hamiltonien à ports, issu du domaine de l’automatique, pour déduire les conditions de raccord dans le cadre l’équation de Saint-Venant et de l’équation de la chaleur non-linéaire. Après une étude analytique de la convergence de la DDM associée à ces conditions de transmission, nous proposons et étudions une formulation de Lagrangien augmenté sous l’hypothèse de séparabilité de la contrainte. / Complexification of multi-physics modeling leads to have to simulate systems of ordinary differential equations and algebraic differential equations with increasingly large numbers of unknowns and over large times of simulation. In addition the evolution of parallel computing architectures requires other ways of parallelization than the decomposition of system in subsystems. In this work, we propose to design domain decomposition methods in time for the resolution of EDO. We reformulate the initial value problem in a boundary values problem on the symmetrized time interval, under the assumption of reversibility of the flow. We develop two methods, the first connected with a Schur complement method, the second based on a Schwarz type method for which we show convergence, being able to be accelerated by the Aitken method within the linear framework. In order to accelerate the convergence of the latter within the non-linear framework, we introduce the techniques of extrapolation and of acceleration of the convergence of non-linear sequences. We show the advantages and the limits of these techniques. The obtained results lead us to develop the acceleration of the method of the type Schwarz by a Newton method. Finally we investigate non-linear matching conditions adapted to the domain decomposition of nonlinear problems. We make use of the port-Hamiltonian formalism, resulting from the control field, to deduce the matching conditions in the framework of the shallow-water equation and the non-linear heat equation. After an analytical study of the convergence of the DDM associated with these conditions of transmission, we propose and study a formulation of augmented Lagrangian under the assumption of separability of the constraint.

La complexification de la modélisation multi-physique conduit d'une part à devoir simuler des systèmes d'équations différentielles ordinaires et d'équations différentielles algébriques de plus en plus grands en nombre d'inconnues et sur des temps de simulation longs. D'autre part l'évolution des architectures de calcul parallèle nécessite d'autres voies de parallélisation que la décomposition de système en sous-systèmes. Dans ce travail, nous proposons de concevoir des méthodes de décomposition de domaine pour la résolution d'EDO en temps. Nous reformulons le problème à valeur initiale en un problème aux valeurs frontières sur l'intervalle de temps symétrisé, sous l'hypothèse de réversibilité du flot. Nous développons deux méthodes, la première apparentée à une méthode de complément de Schur, la seconde basée sur une méthode de type Schwarz dont nous montrons la convergence pouvant être accélérée par la méthode d'Aitken dans le cadre linéaire. Afin d'accélérer la convergence de cette dernière dans le cadre non-linéaire, nous introduisons les techniques d'extrapolation et d'accélération de la convergence des suites non-linéaires. Nous montrons les avantages et les limites de ces techniques. Les résultats obtenus nous conduisent à développer l'accélération de la méthode de type Schwarz par une méthode de Newton. Enfin nous nous intéressons à l'étude de conditions de raccord non-linéaires adaptées à la décomposition de domaine de problèmes non-linéaires. Nous nous servons du formalisme hamiltonien à ports, issu du domaine de l'automatique, pour déduire les conditions de raccord dans le cadre l'équation de Saint-Venant et de l'équation de la chaleur non-linéaire. Après une étude analytique de la convergence de la DDM associée à ces conditions de transmission, nous proposons et étudions une formulation de Lagrangien augmenté sous l'hypothèse de séparabilité de la contrainte.

Cette thèse porte sur la simulation numérique de modèles couplés pour l'écoulement et le transport dans les milieux poreux. Nous présentons une nouvelle méthode de couplage entre les réactions chimiques et le transport en utilisant une méthode de Newton-Krylov, et nous étudions également un modèle d'écoulement en milieu fracturé qui traite l'intersection des fractures par une méthode de décomposition de domaine. <br /> Ce travail est divisé en trois parties : la première partie contient une analyse de différents schémas numériques pour la discrétisation des problèmes d'advection-diffusion, notamment par une technique de séparation d'opérateurs, ainsi que leur mise en oeuvre informatique, dans un code industriel.<br /> La deuxième partie, qui est la contribution majeure de cette thèse, est consacrée à la modélisation et à l'implémentation d'une méthode de couplage globale pour le transport réactif. Le système couplé transport-chimie est décrit, après discrétisation en temps, par un système d'équations non linéaires. La taille du système sous-jacent, à savoir le nombre de points de grille multiplié par le nombre d'espèces chimiques, interdit la résolution du système linéaire par une méthode directe. Pour remédier à cette difficulté, nous utilisons une méthode de Newton-Krylov qui évite de former et de factoriser la matrice Jacobienne. <br /> Dans la dernière partie, nous présentons un modèle d'écoulement dans un milieu fracturé tridimensionnel, basé sur une méthode de décomposition de domaine, et qui traite l'intersection des fractures. Nous démontrons l'existence et l'unicité de la solution, et nous validons le modèle par des tests numériques.

La simulation numérique de systèmes d’équations différentielles raides ordinaires ou algébriques est devenue partie intégrante dans le processus de conception des systèmes mécaniques à dynamiques complexes. L’objet de ce travail est de développer des méthodes numériques pour réduire les temps de calcul par le parallélisme en suivant deux axes : interne à l’intégrateur numérique, et au niveau de la décomposition de l’intervalle de temps. Nous montrons l’efficacité limitée au nombre d’étapes de la parallélisation à travers les méthodes de Runge-Kutta et DIMSIM. Nous développons alors une méthodologie pour appliquer le complément de Schur sur le système linéarisé intervenant dans les intégrateurs par l’introduction d’un masque de dépendance construit automatiquement lors de la mise en équations du modèle. Finalement, nous étendons le complément de Schur aux méthodes de type "Krylov Matrix Free". La décomposition en temps est d’abord vue par la résolution globale des pas de temps dont nous traitons la parallélisation du solveur non-linéaire (point fixe, Newton-Krylov et accélération de Steffensen). Nous introduisons les méthodes de tirs à deux niveaux, comme Parareal et Pita dont nous redéfinissons les finesses de grilles pour résoudre les problèmes raides pour lesquels leur efficacité parallèle est limitée. Les estimateurs de l’erreur globale, nous permettent de construire une extension parallèle de l’extrapolation de Richardson pour remplacer le premier niveau de calcul. Et nous proposons une parallélisation de la méthode de correction du résidu. / This PhD Thesis deals with the development of parallel numerical methods for solving Ordinary and Algebraic Differential Equations. ODE and DAE are commonly arising when modeling complex dynamical phenomena. We first show that the parallelization across the method is limited by the number of stages of the RK method or DIMSIM. We introduce the Schur complement into the linearised linear system of time integrators. An automatic framework is given to build a mask defining the relationships between the variables. Then the Schur complement is coupled with Jacobian Free Newton-Krylov methods. As time decomposition, global time steps resolutions can be solved by parallel nonlinear solvers (such as fixed point, Newton and Steffensen acceleration). Two steps time decomposition (Parareal, Pita,...) are developed with a new definition of their grids to solved stiff problems. Global error estimates, especially the Richardson extrapolation, are used to compute a good approximation for the second grid. Finally we propose a parallel deferred correction

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A engenharia geotécnica é uma das grandes áreas da engenharia civil que estuda a interação entre as construções realizadas pelo homem ou de fenômenos naturais com o ambiente geológico, que na grande maioria das vezes trata-se de solos parcialmente saturados. Neste sentido, o desempenho de obras como estabilização, contenção de barragens, muros de contenção, fundações e estradas estão condicionados a uma correta predição do fluxo de água no interior dos solos. Porém, como a área das regiões a serem estudas com relação à predição do fluxo de água são comumente da ordem de quilômetros quadrados, as soluções dos modelos matemáticos exigem malhas computacionais de grandes proporções, ocasionando sérias limitações associadas aos requisitos de memória computacional e tempo de processamento. A fim de contornar estas limitações, métodos numéricos eficientes devem ser empregados na solução do problema em análise. Portanto, métodos iterativos para solução de sistemas não lineares e lineares esparsos de grande porte devem ser utilizados neste tipo de aplicação. Em suma, visto a relevância do tema, esta pesquisa aproximou uma solução para a equação diferencial parcial de Richards pelo método dos volumes finitos em duas dimensões, empregando o método de Picard e Newton com maior eficiência computacional. Para tanto, foram utilizadas técnicas iterativas de resolução de sistemas lineares baseados no espaço de Krylov com matrizes pré-condicionadoras com a biblioteca numérica Portable, Extensible Toolkit for Scientific Computation (PETSc). Os resultados indicam que quando se resolve a equação de Richards considerando-se o método de PICARD-KRYLOV, não importando o modelo de avaliação do solo, a melhor combinação para resolução dos sistemas lineares é o método dos gradientes biconjugados estabilizado mais o pré-condicionador SOR. Por outro lado, quando se utiliza as equações de van Genuchten deve ser optar pela combinação do método dos gradientes conjugados em conjunto com pré-condicionador SOR. Quando se adota o método de NEWTON-KRYLOV, o método gradientes biconjugados estabilizado é o mais eficiente na resolução do sistema linear do passo de Newton, com relação ao pré-condicionador deve-se dar preferência ao bloco Jacobi. Por fim, há evidências que apontam que o método PICARD-KRYLOV pode ser mais vantajoso que o método de NEWTON-KRYLOV, quando empregados na resolução da equação diferencial parcial de Richards. / Geotechnical Engineering is the area of Civil Engineering that studies the interaction between constructions carried out by man or natural phenomena with geological environment, which most of times is partially saturated soil. In this sense, work developing as stabilization, dam containing, retaining walls, foundations and highways are conditioned to a right prediction of water flow into the soil. However, considering the water flow, the studied region areas are commonly on the order of square kilometers, mathematical models solutions require computational meshes of large proportions, causing serious limitations linked to computational memory requirements and processing time. In order to overcome these limitations, efficient numerical methods must be used in the solution of the considered problem. Hence iterative methods for solving nonlinear and large sparse linear systems must be used in this type of application. In short, this study approached a solution to the Richard partial differential equation by the two dimensions finite volume method, bringing Picard and Newton method with greater efficiency. Linear system resolution iterative techniques based on Krylov space with pre-conditioners matrix were used. Portable Extensible Toolkit for Scientific Computation (PETSc) numerical library was a tool used during the task. The results indicate when a Richards equation is solved considering thr PICARD-KRYLOV method, no matter the soil evaluation model, the best combination for solving linear systems is the stabilized double gradient method and the SOR preconditioning. On the other hand, when the van Genuchten equations are used the gradients methods with the SOR preconditioning must be chosen. Adopting the NEWTON-KRYLOV method, the stabilized double gradient method is more efficient in soling Newton linear system, in relation to the preconditioning it must be giving preference to the Jacob block. Finally, there are strong indications that the PICARDKRYLOV method can be more effective than the NEWTON-KRYLOV one, when used for solving Richards partial differential equation.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A engenharia geotécnica é uma das grandes áreas da engenharia civil que estuda a interação entre as construções realizadas pelo homem ou de fenômenos naturais com o ambiente geológico, que na grande maioria das vezes trata-se de solos parcialmente saturados. Neste sentido, o desempenho de obras como estabilização, contenção de barragens, muros de contenção, fundações e estradas estão condicionados a uma correta predição do fluxo de água no interior dos solos. Porém, como a área das regiões a serem estudas com relação à predição do fluxo de água são comumente da ordem de quilômetros quadrados, as soluções dos modelos matemáticos exigem malhas computacionais de grandes proporções, ocasionando sérias limitações associadas aos requisitos de memória computacional e tempo de processamento. A fim de contornar estas limitações, métodos numéricos eficientes devem ser empregados na solução do problema em análise. Portanto, métodos iterativos para solução de sistemas não lineares e lineares esparsos de grande porte devem ser utilizados neste tipo de aplicação. Em suma, visto a relevância do tema, esta pesquisa aproximou uma solução para a equação diferencial parcial de Richards pelo método dos volumes finitos em duas dimensões, empregando o método de Picard e Newton com maior eficiência computacional. Para tanto, foram utilizadas técnicas iterativas de resolução de sistemas lineares baseados no espaço de Krylov com matrizes pré-condicionadoras com a biblioteca numérica Portable, Extensible Toolkit for Scientific Computation (PETSc). Os resultados indicam que quando se resolve a equação de Richards considerando-se o método de PICARD-KRYLOV, não importando o modelo de avaliação do solo, a melhor combinação para resolução dos sistemas lineares é o método dos gradientes biconjugados estabilizado mais o pré-condicionador SOR. Por outro lado, quando se utiliza as equações de van Genuchten deve ser optar pela combinação do método dos gradientes conjugados em conjunto com pré-condicionador SOR. Quando se adota o método de NEWTON-KRYLOV, o método gradientes biconjugados estabilizado é o mais eficiente na resolução do sistema linear do passo de Newton, com relação ao pré-condicionador deve-se dar preferência ao bloco Jacobi. Por fim, há evidências que apontam que o método PICARD-KRYLOV pode ser mais vantajoso que o método de NEWTON-KRYLOV, quando empregados na resolução da equação diferencial parcial de Richards. / Geotechnical Engineering is the area of Civil Engineering that studies the interaction between constructions carried out by man or natural phenomena with geological environment, which most of times is partially saturated soil. In this sense, work developing as stabilization, dam containing, retaining walls, foundations and highways are conditioned to a right prediction of water flow into the soil. However, considering the water flow, the studied region areas are commonly on the order of square kilometers, mathematical models solutions require computational meshes of large proportions, causing serious limitations linked to computational memory requirements and processing time. In order to overcome these limitations, efficient numerical methods must be used in the solution of the considered problem. Hence iterative methods for solving nonlinear and large sparse linear systems must be used in this type of application. In short, this study approached a solution to the Richard partial differential equation by the two dimensions finite volume method, bringing Picard and Newton method with greater efficiency. Linear system resolution iterative techniques based on Krylov space with pre-conditioners matrix were used. Portable Extensible Toolkit for Scientific Computation (PETSc) numerical library was a tool used during the task. The results indicate when a Richards equation is solved considering thr PICARD-KRYLOV method, no matter the soil evaluation model, the best combination for solving linear systems is the stabilized double gradient method and the SOR preconditioning. On the other hand, when the van Genuchten equations are used the gradients methods with the SOR preconditioning must be chosen. Adopting the NEWTON-KRYLOV method, the stabilized double gradient method is more efficient in soling Newton linear system, in relation to the preconditioning it must be giving preference to the Jacob block. Finally, there are strong indications that the PICARDKRYLOV method can be more effective than the NEWTON-KRYLOV one, when used for solving Richards partial differential equation.

[pt] Neste trabalho focamos sobre alguns modelos matemáticos na área do petróleo, com o objetivo de propor um modelo inicial de simulador numérico de reservatórios. Inicialmente apresentamos uma EDP do calor não-linear com um termo fonte de calor constante, estudada para o domínio sendo uma placa plana quadrada homogênea e heterogênea, onde aplicamos soluções numéricas utilizando o método das diferenças finitas implícito. Abordamos o problema de refinamento da malha no entorno dos poços utilizando o método JFNK (Jacobian-Free Newton-Krylov), que aumenta a eficiência computacional através de uma aproximação para a matriz Jacobiana. Por fim resolvemos um sistema de EDPs não-lineares que representam o escoamento bifásico de água e óleo, constituído por equações de transporte em termos da pressão e da saturação. Fizemos simulações numéricas de alguns casos conhecidos e os resultados mostraram uma boa qualidade no nosso método. / [en] In this work we focus on the numerical approximation of some mathematical models in the oil field. First, we present a non-linear heat equation with a constant heat source term, studied for the domain of a homogeneous and heterogeneous square domain, where we apply numerical solutions using an implicit finite difference method. We approach the problem of mesh refinement around the wells using the JFNK (Jacobian- Free Newton-Krylov) method, which improves the computational efficiency through an approximation to the Jacobian matrix. Finally, we solve a system of non-linear EDPs that represent the two-phase flow of water and oil, consisting of equations of transport in terms of pressure and saturation. Numerical simulations for some known cases showed accurate approximation of our method.