Robust preconditioners on block-triangular and block-factorized form for three types of linear systems of two-by-two block form are studied in this thesis. The first type of linear systems, which are dense, arise from a boundary element type of discretization of crack propagation problems. Numerical experiment show that simple algebraic preconditioning strategies results in iterative schemes that are highly competitive with a direct solution method. The second type of algebraic systems, which are sparse, indefinite and nonsymmetric, arise from a finite element (FE) discretization of the partial differential equations (PDE) that describe (visco)elastic glacial isostatic adjustment (GIA). The Schur complement approximation in the block preconditioners is constructed by assembly of local, exactly computed Schur matrices. The quality of the approximation is verified in numerical experiments. When the block preconditioners for the indefinite problem are combined with an inner iterative scheme preconditioned by a (nearly) optimal multilevel preconditioner, the resulting preconditioner is (nearly) optimal and robust with respect to problem size, material parameters, number of space dimensions, and coefficient jumps. Two approaches to mathematically formulate the PDEs for GIA are compared. In the first approach the equations are formulated in their full complexity, whereas in the second their formulation is confined to the features and restrictions of the employed FE package. Different solution methods for the algebraic problem are used in the two approaches. Analysis and numerical experiments reveal that the first strategy is more accurate and efficient than the latter. The block structure in the third type of algebraic systems is due to a fine-coarse splitting of the unknowns. The inverse of the pivot block is approximated by a sparse matrix which is assembled from local, exactly inverted matrices. Numerical experiments and analysis of the approximation show that it is robust with respect to problem size and coefficient jumps.

Cette thèse présente une vision unifiée de plusieurs méthodes de décomposition de domaine : celles avec recouvrement, dites de Schwarz, et celles basées sur des compléments de Schur, dites de sous-structuration. Il est ainsi possible de changer de méthodes de manière abstraite et de construire différents préconditionneurs pour accélérer la résolution de grands systèmes linéaires creux par des méthodes itératives. On rencontre régulièrement ce type de systèmes dans des problèmes industriels ou scientifiques après discrétisation de modèles continus. Bien que de tels préconditionneurs exposent naturellement de bonnes propriétés de parallélisme sur les architectures distribuées, ils peuvent s’avérer être peu performants numériquement pour des décompositions complexes ou des problèmes physiques multi-échelles. On peut pallier ces défauts de robustesse en calculant de façon concurrente des problèmes locaux creux ou denses aux valeurs propres généralisées. D’aucuns peuvent alors identifier des modes qui perturbent la convergence des méthodes itératives sous-jacentes a priori. En utilisant ces modes, il est alors possible de définir des opérateurs de projection qui utilisent un problème dit grossier. L’utilisation de ces outils auxiliaires règle généralement les problèmes sus-cités, mais tend à diminuer les performances algorithmiques des préconditionneurs. Dans ce manuscrit, on montre en trois points quela nouvelle construction développée est performante : 1) grâce à des essais numériques à très grande échelle sur Curie—un supercalculateur européen, puis en le comparant à des solveurs de pointe 2) multi-grilles et 3) directs. / This thesis introduces a unified framework for various domain decomposition methods:those with overlap, so-called Schwarz methods, and those based on Schur complements,so-called substructuring methods. It is then possible to switch with a high-level of abstractionbetween methods and to build different preconditioners to accelerate the iterativesolution of large sparse linear systems. Such systems are frequently encountered in industrialor scientific problems after discretization of continuous models. Even though thesepreconditioners naturally exhibit good parallelism properties on distributed architectures,they can prove inadequate numerical performance for complex decompositions or multiscalephysics. This lack of robustness may be alleviated by concurrently solving sparse ordense local generalized eigenvalue problems, thus identifying modes that hinder the convergenceof the underlying iterative methods a priori. Using these modes, it is then possibleto define projection operators based on what is usually referred to as a coarse solver. Theseauxiliary tools tend to solve the aforementioned issues, but typically decrease the parallelefficiency of the preconditioners. In this dissertation, it is shown in three points thatthe newly developed construction is efficient: 1) by performing large-scale numerical experimentson Curie—a European supercomputer, and by comparing it with state of the art2) multigrid and 3) direct solvers.

Boundary Approximation Method (BAM), or the Collocation Trefftz Method called in the literature, is the most efficient method to solve elliptic boundary value problems with singularities. There are several versions of BAM in practical computation, including the Numerical BAM, Symbolic BAM and their variants. It is known that the Symbolic BAM is much slower than Numerical counterpart. In this thesis, we improve the Symbolic BAM to become the fastest method among all versions of BAM. We prove several important lemmas to reduce the computing time, and a recursive procedure is found to expedite the evaluation of major integrals. Another drawback of the Symbolic BAM is its large condition number. We find a good and easy preconditioner to significantly reduce the condition number. The numerical experiments and comparison are also provided for the Motz problem, a prototype of Laplace boundary value problem with singularity, and the Schiff's Model, a prototype of biharmonic boundary value problem with singularity.

We use Darcy's law and conservation of mass to model the flow of a fluid through a porous medium. It is a second order elliptic system with a heterogeneous coefficient. We consider the equations written in mixed form. In the heterogeneous case, we define a new multiscale mortar space that incorporates purely local information from homogenization theory to better approximate the solution along the interfaces with just a few degrees of freedom. In the case of a locally periodic heterogeneous coefficient of period epsilon, we prove that the new method achieves both optimal order error estimates in the discretization parameters and good approximation when epsilon is small. Moreover, we present numerical examples to assess its performance when the coefficient is not obviously locally periodic. We show that the new mortar method works well, and better than polynomial mortar spaces. On the other hand, we also propose to use multiscale mortars as a coarse component to construct a two-level preconditioner for the saddle point linear system arising from the fine scale discretization of the mixed finite element system. The two-level preconditioners are constructed based on the interfaces. We propose a framework to define the interpolation operators for the face based two-level preconditioners for different combination of coarse and fine scale mortar spaces for matching and nonmatching grids. In this dissertation, we show that for quasi-homogeneous problems and matching grids, the condition number of the preconditioned interface operator is bounded by (log(H/h))², which is the same as the traditional two-level preconditioners, for quasi-homogeneous problems. We show several numerical examples to demonstrate that for the strongly heterogeneous porous media, it is often desirable and even necessary to use a higher dimensional coarse mortar space to construct the coarse preconditioner to achieve convergence. We apply our ideas to study slightly compressible single phase and two-phase flow in a porous medium. We find that for the nonlinear single phase problem, the two-level preconditioners could be successfully applied to the symmetrized linear system. For the two-phase problem, using the fine scale, instead of multiscale, velocity solutions from the flow problem can greatly benefit the transport problem. / text

Aerodynamic shape optimization and multidisciplinary optimization algorithms have the potential not only to improve conventional aircraft, but also to enable the design of novel configurations. By their very nature, these algorithms generate and analyze a large number of unique shapes, resulting in high computational costs. In order to improve their efficiency and enable their use in the early stages of the design process, a fast and robust flow solution algorithm is necessary. This thesis presents an efficient parallel Newton-Krylov-Schur flow solution algorithm for the three-dimensional Navier-Stokes equations coupled with the Spalart-Allmaras one-equation turbulence model. The algorithm employs second-order summation-by-parts (SBP) operators on multi-block structured grids with simultaneous approximation terms (SATs) to enforce block interface coupling and boundary conditions. The discrete equations are solved iteratively with an inexact-Newton method, while the linear system at each Newton iteration is solved using the flexible Krylov subspace iterative method GMRES with an approximate-Schur parallel preconditioner. The algorithm is thoroughly verified and validated, highlighting the correspondence of the current algorithm with several established flow solvers. The solution for a transonic flow over a wing on a mesh of medium density (15 million nodes) shows good agreement with experimental results. Using 128 processors, deep convergence is obtained in under 90 minutes. The solution of transonic flow over the Common Research Model wing-body geometry with grids with up to 150 million nodes exhibits the expected grid convergence behavior. This case was completed as part of the Fifth AIAA Drag Prediction Workshop, with the algorithm producing solutions that compare favourably with several widely used flow solvers. The algorithm is shown to scale well on over 6000 processors. The results demonstrate the effectiveness of the SBP-SAT spatial discretization, which can be readily extended to high order, in combination with the Newton-Krylov-Schur iterative method to produce a powerful parallel algorithm for the numerical solution of the Reynolds-averaged Navier-Stokes equations. The algorithm can efficiently solve the flow over a range of clean geometries, making it suitable for use at the core of an optimization algorithm.

Aerodynamic shape optimization and multidisciplinary optimization algorithms have the potential not only to improve conventional aircraft, but also to enable the design of novel configurations. By their very nature, these algorithms generate and analyze a large number of unique shapes, resulting in high computational costs. In order to improve their efficiency and enable their use in the early stages of the design process, a fast and robust flow solution algorithm is necessary. This thesis presents an efficient parallel Newton-Krylov-Schur flow solution algorithm for the three-dimensional Navier-Stokes equations coupled with the Spalart-Allmaras one-equation turbulence model. The algorithm employs second-order summation-by-parts (SBP) operators on multi-block structured grids with simultaneous approximation terms (SATs) to enforce block interface coupling and boundary conditions. The discrete equations are solved iteratively with an inexact-Newton method, while the linear system at each Newton iteration is solved using the flexible Krylov subspace iterative method GMRES with an approximate-Schur parallel preconditioner. The algorithm is thoroughly verified and validated, highlighting the correspondence of the current algorithm with several established flow solvers. The solution for a transonic flow over a wing on a mesh of medium density (15 million nodes) shows good agreement with experimental results. Using 128 processors, deep convergence is obtained in under 90 minutes. The solution of transonic flow over the Common Research Model wing-body geometry with grids with up to 150 million nodes exhibits the expected grid convergence behavior. This case was completed as part of the Fifth AIAA Drag Prediction Workshop, with the algorithm producing solutions that compare favourably with several widely used flow solvers. The algorithm is shown to scale well on over 6000 processors. The results demonstrate the effectiveness of the SBP-SAT spatial discretization, which can be readily extended to high order, in combination with the Newton-Krylov-Schur iterative method to produce a powerful parallel algorithm for the numerical solution of the Reynolds-averaged Navier-Stokes equations. The algorithm can efficiently solve the flow over a range of clean geometries, making it suitable for use at the core of an optimization algorithm.

In this dissertation, we focus on the uncertainty quantification problems where the goal is to sample the porous media properties given integrated responses. We first introduce a reduced order model using the level set method to characterize the channelized features of permeability fields. The sampling process is completed under Bayesian framework. We hence study the regularity of posterior distributions with respect to the prior measures. The stochastic flow equations that contain both spatial and random components must be resolved in order to sample the porous media properties. Some type of upscaling or multiscale technique is needed when solving the flow and transport through heterogeneous porous media. We propose ensemble-level multiscale finite element method and ensemble-level preconditioner technique for solving the stochastic flow equations, when the permeability fields have certain topology features. These methods can be used to accelerate the forward computations in the sampling processes. Additionally, we develop analysis-of-variance-based mixed multiscale finite element method as well as a novel adaptive version. These methods are used to study the forward uncertainty propagation of input random fields. The computational cost is saved since the high dimensional problem is decomposed into lower dimensional problems. We also work on developing efficient advanced Markov Chain Monte Carlo methods. Algorithms are proposed based on the multi-stage Markov Chain Monte Carlo and Stochastic Approximation Monte Carlo methods. The new methods have the ability to search the whole sample space for optimizations. Analysis and detailed numerical results are presented for applications of all the above methods.

The main objective of this project is to develop a "black-box" multigrid preconditioner for the iterative solution of finite element discretisations of the convection-diffusion equation with dominant convection. This equation can be considered a stand alone scalar problem or as part of a more complex system of partial differential equations, such as the Navier-Stokes equations. The project will focus on the stand alone scalar problem. Multigrid is considered an optimal preconditioner for scalar elliptic problems. This strategy can also be used for convection-diffusion problems, however an appropriate robust smoother needs to be developed to achieve mesh-independent convergence. The focus of the thesis is on the development of such a smoother. In this context a novel smoother is developed referred to as truncated incomplete factorisation (tILU) smoother. In terms of computational complexity and memory requirements, the smoother is considerably less expensive than the standard ILU(0) smoother. At the same time, it exhibits the same robustness as ILU(0) with respect to the problem and discretisation parameters. The new smoother significantly outperforms the standard damped Jacobi smoother and is a competitor to the Gauss-Seidel smoother (and in a number of important cases tILU outperforms the Gauss-Seidel smoother). The new smoother depends on a single parameter (the truncation ratio). The project obtains a default value for this parameter and demonstrated the robust performance of the smoother on a broad range of problems. Therefore, the new smoothing method can be regarded as "black-box". Furthermore, the new smoother does not require any particular ordering of the nodes, which is a prerequisite for many robust smoothers developed for convection-dominated convection-diffusion problems. To test the effectiveness of the preconditioning methodology, we consider a number of model problems (in both 2D and 3D) including uniform and complex (recirculating) convection fields discretised by uniform, stretched and adaptively refined grids. The new multigrid preconditioner within block preconditioning of the Navier-Stokes equations was also tested. The numerical results gained during the investigation confirm that tILU is a scalable, robust smoother for both geometric and algebraic multigrid. Also, comprehensive tests show that the tILU smoother is a competitive method.

After some remarks on the parallel implementation of the Finite Element package FEAP, our realisation of the parallel CG-algorithm is sketched. From a technical point of view, a hierarchical preconditioner with and without additional global crosspoint preconditioning is presented. The numerical properties of this preconditioners are discussed and compared to a Schur-complement-preconditioning, using a wide range of data from computations on technical and academic examples from elasticity.

Cette thèse vise à contribuer à l'adoption du virtual testing, pratique industrielle encore embryonnaire qui consistera à optimiser et certifier par la simulation numérique le dimensionnement de pièces industrielles critiques. Le virtual testing permettra des économies colossales dans la conception des pièces mécaniques et un plus grand respect de l'environnement grâce à des designs optimisés. Afin d'atteindre un tel objectif, de nouvelles méthodes de calcul doivent être mises en place, plus sûres, plus respectueuses des architectures matérielles, plus rapides, compatibles avec les contraintes temporelles de l'ingénierie. Nous nous intéressons à la résolution parallèle de problèmes non linéaires de grande taille par des méthodes de décomposition de domaine. Notre objectif est d'atteindre une approximation de la solution exacte en minimisant les communications entre les sous-domaines. Pour cela nous souhaitons maximiser les calculs réalisés indépendamment par sous-domaine à l'aide d'approches de relocalisation non linéaire, contrôler les critères de convergence des solveurs imbriqués de manière à éviter la sur-résolution et les divergences, améliorer la construction de conditions d'interface mixtes, et non linéariser l'étape de préconditionnement du solveur. L'objectif à terme étant de traiter des problèmes de complexité industrielle, la robustesse des méthodes sera un souci constant. De manière classique, les problèmes non linéaires sont résolus en construisant une suite de systèmes linéaires qui peuvent être résolus en parallèle à l'aide de méthodes itératives, telles que les solveurs de Krylov. Nous souhaitons remettre en question cette procédure usuelle en essayant de construire une suite de petits systèmes non linéaires indépendants à résoudre en parallèle. Une telle technique implique l'utilisation de solveurs itératifs imbriqués dont les critères de convergence doivent être syntonisés dynamiquement de manière à éviter à la fois la sur-résolution et la perte de convergence. La robustesse de la méthode pourra notamment être assurée par l'emploi de conditions d'interface mixtes bien construites et de préconditionneurs bien choisis. / This thesis is aimed to contribute to the adoption of virtual testing, an industrial practice still embryonic which consists in optimizing and certifying by numerical simulations the dimensioning of critical industrial structures. The virtual testing will allow colossal savings in the design of mechanical parts and a greater respect for the environment, thanks to optimized designs. In order to achieve this goal, new calculation methods must be implemented, satisfying more requirements concerning safety, respect for hardware architectures, fastness, and compatibility with the time constraints of engineering.We are interested in the parallel resolution of large nonlinear problems by domain decomposition methods. Our goal is to approximate the exact solution by minimizing communication between subdomains. In order to do this, we want to maximize the computations performed independently by subdomain, using nonlinear relocation approaches. We also try to control the convergence criteria of the nested solvers in order to avoid over-resolution and divergences, to improve the construction of conditions Of mixed interface, and non-linearizing the preconditioning step of the solver. The ultimate objective being to deal with problems of industrial complexity, the robustness of the methods we develop will be a constant concern.Conventionally, non-linear problems are solved by constructing a sequence of linear systems that can be solved in parallel using iterative methods, such as Krylov solvers. We wish to question this usual procedure by trying to construct a sequence of small independent nonlinear systems to be solved in parallel. Such a technique involves the use of interleaved iterative solvers, whose convergence criteria must be dynamically tuned in order to avoid both over-resolution and loss of convergence. The robustness of the method can be ensured in particular by the use of well-constructed mixed interface conditions and well-chosen preconditioners;