O objetivo principal deste trabalho é a paralelização de um modelo global de previsão do tempo em diferenças finitas com refinamento local. Este é baseado nas equações primitivas, e faz uso de uma discretização semi-Lagrangiana e semi-implícita em três níveis no tempo em uma malha de Lorenz na vertical e uma malha do tipo C de Arakawa na horizontal. A discretização horizontal é feita através de diferenças finitas de segunda ordem. A equação escalar elíptica tridimensional resultante é desacoplada em um sistema de equações bidimensionais do tipo Helmholtz, o qual é resolvido por meio de um método multigrid. O modelo de paralelização foi desenvolvido para máquinas com memória distribuída, fazendo uso de MPI para passagens de mensagens e baseado em técnicas de decomposição de domínio. O acoplamento apenas local dos operadores de diferenças finitas viabiliza a decomposição em duas direções horizontais. Evitamos a decomposição vertical, tendo em vista o forte acoplamento nesta direção das parametrizações de fenômenos físicos. A estratégia de paralelização foi elaborada visando o uso eficiente de centenas ou alguns milhares de processadores, dependendo da resolução do modelo. Para tal, a malha localmente refinada é separada em três regiões: uma grossa, uma de transição e uma fina, onde cada uma delas é dividida de forma independente entre um número de processadores proporcional ao número de pontos que cada uma armazena, garantindo assim um balanceamento de carga adequado. Não obstante, para resolver o sistema de equações bidimensionais do tipo Helmholtz foi necessário mudar a estratégia de paralelização, dividindo o domínio unicamente nas direções vertical e latitudinal. Ambas partes do modelo com paralelizações diferentes estão conectadas por meio da estratégia de transposição de dados. Testamos nosso modelo utilizando até 1024 processadores e os resultados ainda mostraram uma boa escalabilidade. / The main goal of this work is the parallelization of a weather prediction model employing finite differences on locally refined meshes. The model is based on the primitive equations and uses a three-time-level semi-implicit semi-Lagrangian temporal discretization on a Lorenz-type vertical grid combined with a horizontal Arakawa C-grid. The horizontal discretization is performed by means of second order finite differences. The resulting three-dimensional scalar elliptic equation is decoupled into a set of Helmholtz-type two-dimensional equations, solved by a multigrid method. The parallelization has been written for distributed-memory machines, employing the MPI message passing standard and was based on domain decomposition techniques. The local coupling of the finite difference operators was exploited in a two-dimensional horizontal decomposition. We avoid a vertical decomposition due to the strong coupling of physical parameterization routines. The parallelization strategy has been designed in order to allow the efficient use of hundreds to a few thousand processors, depending on the model resolution. In order to achieve this, the locally refined mesh is split into three regions: a coarse, a transition and a fine one, each decomposed independently. The number of allocated processors for each region is proportional to the number of the grid-points it contains, in order to guarantee a good load-balancing distribution. However, to solve the set of Helmholtz-type bidimensional equations it was necessary to change the parallelization strategy, splitting the domain only in vertical and latitudinal directions. Both parts of the model with different parallelizations are related by means the data transposition strategy. We tested our model using up to 1024 processors and the results still showed a good scalability.

In the recent past, the field of scientific computing has become of more and more importance for scientific as well as for industrial research, playing a comparable role as experiment and theory do. This success of computational methods in scientific and engineering research is next to the enormous improvement of computer hardware to a large extend due to contributions from applied mathematicians, who have developed algorithms which make real life applications feasible. Examples are adaptive methods, high order discretization, fast linear and non-linear solvers and multi-level methods. The application of these methods in a large class of problems demands for suitable and robust tools for a flexible and efficient implementation. In order to play a crucial role in scientific and engineering research, besides efficiency in the numerical solution, also efficiency in problem setup and interpretation of simulation results is of utmost importance. As modeling and computing comes closer together, efficient computational methods need to be applied to new sets of equations. The problems to be addressed by simulation methods become more and more complicated, ranging over different scales, interacting on different dimensions and combining different physics. Such problems need to be implemented in a short period of time, solved on complicated domains and visualized with respect to the demand of the user. %Only a modular abstract simulation environment will fulfill these requirements and allow to setup, solve and visualize real-world problems appropriately. In this work, the concepts and the design of the C++ finite element toolbox AMDiS (adaptive multidimensional simulations) are described. It is shown, how abstract data structures and modern software concepts can help to design user-friendly finite element software, which provides large flexibility in problem definition while on the other hand efficiently solves these problems. Also systems of coupled problems can be solved in an intuitive way. In order to demonstrate its possibilities, AMDiS has been applied to several non-standard problems. The most time-consuming part in most simulations is the solution of linear systems of equations. Multi-level methods use discretization hierarchies to solve these systems in a very efficient way. In AMDiS, such multi-level techniques are implemented in the context of adaptive finite elements. Several numerical results are given which compare this multigrid solver with classical iterative methods. Besides the development of more efficient algorithms also the growing hardware capabilities lead to an improvement of simulation possibilities. Modern computing clusters contain more and more processors and also personal computers today are often equipped with multi-core processors. In this work, a new parallelization approach has been developed which allows the parallelization of sequential code in a very easy way and reduces the communication overhead compared to classical parallelization concepts.

This thesis treats two essentially different subjects: V-cycle schemes are considered in Chapters 2-4, whereas the aggregation-based coarsening is analysed in Chapters 5-6. As a matter of paradox, these two multigrid ingredients, when combined together, can hardly lead to an optimal algorithm. Indeed, a V-cycle needs more accurate prolongations than the simple piecewise-constant one, associated to aggregation-based coarsening. On the other hand, aggregation-based approaches use almost exclusively piecewise constant prolongations, and therefore need more involved cycling strategies, K-cycle <a href=http://www3.interscience.wiley.com/journal/114286660/abstract?CRETRY=1&SRETRY=0>[Num.Lin.Alg.Appl., vol.15(2008), pp.473-487]</a> being an attractive alternative in this respect. <br> <br> Chapter 2 considers more precisely the well-known V-cycle convergence theories: the approximation property based analyses by Hackbusch (see [Multi-Grid Methods and Applications, 1985, pp.164-167]) and by McCormick [SIAM J.Numer.Anal., vol.22(1985), pp.634-643] and the successive subspace correction theory, as presented in [SIAM Review, vol.34(1992), pp.581-613] by Xu and in [Acta Numerica, vol.2(1993), pp.285-326.] by Yserentant. Under the constraint that the resulting upper bound on the convergence rate must be expressed with respect to parameters involving two successive levels at a time, these theories are compared. Unlike [Acta Numerica, vol.2(1993), pp.285-326.], where the comparison is performed on the basis of underlying assumptions in a particular PDE context, we compare directly the upper bounds. We show that these analyses are equivalent from the qualitative point of view. From the quantitative point of view, we show that the bound due to McCormick is always the best one. <br> <br> When the upper bound on the V-cycle convergence factor involves only two successive levels at a time, it can further be compared with the two-level convergence factor. Such comparison is performed in Chapter 3, showing that a nice two-grid convergence (at every level) leads to an optimal McCormick's bound (the best bound from the previous chapter) if and only if a norm of a given projector is bounded on every level. <br> <br> In Chapter 4 we consider the Fourier analysis setting for scalar PDEs and extend the comparison between two-grid and V-cycle multigrid methods to the smoothing factor. In particular, a two-sided bound involving the smoothing factor is obtained that defines an interval containing both the two-grid and V-cycle convergence rates. This interval is narrow when an additional parameter α is small enough, this latter being a simple function of Fourier components. <br> <br> Chapter 5 provides a theoretical framework for coarsening by aggregation. An upper bound is presented that relates the two-grid convergence factor with local quantities, each being related to a particular aggregate. The bound is shown to be asymptotically sharp for a large class of elliptic boundary value problems, including problems with anisotropic and discontinuous coefficients. <br> <br> In Chapter 6 we consider problems resulting from the discretization with edge finite elements of 3D curl-curl equation. The variables in such discretization are associated with edges. We investigate the performance of the Reitzinger and Schöberl algorithm [Num.Lin.Alg.Appl., vol.9(2002), pp.223-238], which uses aggregation techniques to construct the edge prolongation matrix. More precisely, we perform a Fourier analysis of the method in two-grid setting, showing its optimality. The analysis is supplemented with some numerical investigations.

Implementamos um algoritmo de multi-grid em dois códigos de elementos finitos. Um deles resolve problemas unidimensionais e, o outro, bidimensionais. O algoritmo se baseia no conceito de bases hierárquicas. Desenvolvemos uma estrutura de dados que facilita bastante o cômputo dos operadores de restrição e interpolação. Os programas de elementos finitos foram testados em diferentes problemas de valor no contorno. Os resultados obtifdos foram apresentados em gráficos, confirmando a eficiência do método de multi-grid para acelerar a convergência dos processos iterativos de Jacobi, Gauss-Seidel e gradiente conjugado na resolução de problemas elípticos.

This thesis investigates three problems relating to thermoconvective stability in porous media. These are (i) the stability of an inclined boundary layer flow to vortex type instability, (ii) front propagation in the Darcy-B´enard problem and (iii) the onset of Prantdl-Darcy convection in a horizontal porous layer subject to a horizontal pressure gradient. The nonlinear, elliptic governing equations for the inclined boundary layer flow are discretised using finite differences and solved using an implicit, MultiGrid Full Approximation Scheme. In addition to the basic steady state three configurations are examined: (i) unforced disturbances, (ii) global forced disturbances, and (iii) leading edge forced disturbances. The unforced inclined boundary layer is shown to be convectively unstable to vortex-type instabilities. The forced vortex system is found to produce critical distances in good agreement with parabolic simulations. The speed of propagation and the pattern formed behind a propagating front in the Darcy-B´enard problem are examined using weakly nonlinear analysis and through numerical solution of the fully nonlinear governing equations for both two and three dimensional flows. The unifying theory of Ebert and van Saarloos (Ebert and van Saarloos (1998)) for pulled fronts is found to describe the behaviour well in two dimensions, but the situation in three dimensions is more complex with combinations of transverse and longitudinal rolls occurring. A linear perturbation analysis of the onset of Prandtl-Darcy convection in a horizontal porous layer subject to a horizontal pressure gradient indicates that the flow becomes more stable as the underlying flow increases, and that the wavelength of the most dangerous disturbances also increases with the strength of the underlying flow. Asymptotic analyses for small and large underlying flow and large Prandtl number are carried out and results compared to those of the linear perturbation analysis.

The main purpose of the dissertation is to contribute to the development of numerical techniques for computational heat transfer and fluid flow, suitable for low cost (loosely coupled) parallel computers. It is focused on implicit integration schemes, using finite control volumes with multigrid (MG) algorithms.Natural convection in closed cavities is used as a problem model to introduce different aspects related with the integration of the incompressible Navier-Stokes equations, such as the solution of the pressure correction (or similar) equations that is the bottleneck of the algorithms for parallel computers. The main goal of the dissertation has been to develop new algorithms to advance in the solution of this problem rather than to implement a complete parallel CFD code. An overview of different sequential multigrid algorithms is presented, pointing out the difference between geometric and algebraic multigrid. A detailed description of segregated ACM is given. The direct simulation of a turbulent natural convection flow is presented as an application example. A short description of the coupled ACM variant is given.Background information of parallel computing technology is provided and the the key aspects for its efficient use in CFD are discussed. The limitations of low cost, loosely coupled cost parallel computers (high latency and low bandwidth) are introduced. An overview of different control-volume based PCFD and linear equation solvers is done. As an example, a code to solve reactive flows using Schwartz Alternating Method that runs particularly well on Beowulf clusters is given.Different alternatives for latency-tolerant parallel multigrid are examined, mainly the DDV cycle proposed by Brandt and Diskin in a theoretical paper. One of its main features is that, supressing pre-smoothing, it allows to reduce the each-to-neighbours communications to one per MG iteration. In the dissertation, the cycle is extended to two-dimensional domain decompositions. The effect of each of its features is separately analyzed, concluding that the use of a direct solver for the coarsest level and the overlapping areas are important aspects. The conclusion is not so clear respect to the suppression of the pre-smoothing iterations.A very efficient direct method to solve the coarser MG level is needed for efficient parallel MG. In this work, variant of the Schur complement algorithm, specific for relatively small, constant matrices has been developed. It is based on the implicit solution of the interfaces of the processors subdomains. In the implementation proposed in this work, a parallel evaluation and storage of the inverse of the interface matrix is used. The inner nodes of each domain are also solved with a direct algorithm. The resulting algorithm, after a pre-processing stage, allows a very efficient solution of pressure correction equations of incompressible flows in loosely coupled parallel computers.Finally, all the elements presented in the work are combined in the DDACM algorithm, an algebraic MG equivalent to the DDV cycle, that is as a combination of a parallel ACM algorithm with BILU smoothing and a specific version of the Schur complement direct solver. It can be treated as a black-box linear solver and tailored to different parallel architectures.The parallel algorithms analysed (different variants of V cycle and DDV) and developed in the work (a specific version of the Schur complement algorithm and the DDACM multigrid algorithm) are benchmarked using a cluster of 16 PCs with a switched 100 Mbits/s network.The general conclusion is that the algorithms developed are suitable options to solve the pressure correction equation, that is the main bottleneck for the solution of implicit flows on loosely coupled parallel computers.

The modeling of electromagnetic phenomena described by the Maxwell's equations is of critical importance in many practical applications. The numerical simulation of these equations is challenging and much more involved than initially believed. Consequently, many discretization techniques, most of them quite complicated, have been proposed. In this dissertation, we present and analyze a new methodology for approximation of the time-harmonic Maxwell's equations. It is an extension of the negative-norm least-squares finite element approach which has been applied successfully to a variety of other problems. The main advantages of our method are that it uses simple, piecewise polynomial, finite element spaces, while giving quasi-optimal approximation, even for solutions with low regularity (such as the ones found in practical applications). The numerical solution can be efficiently computed using standard and well-known tools, such as iterative methods and eigensolvers for symmetric and positive definite systems (e.g. PCG and LOBPCG) and reconditioners for second-order problems (e.g. Multigrid). Additionally, approximation of varying polynomial degrees is allowed and spurious eigenmodes are provably avoided. We consider the following problems related to the Maxwell's equations in the frequency domain: the magnetostatic problem, the electrostatic problem, the eigenvalue problem and the full time-harmonic system. For each of these problems, we present a natural (very) weak variational formulation assuming minimal regularity of the solution. In each case, we prove error estimates for the approximation with two different discrete least-squares methods. We also show how to deal with problems posed on domains that are multiply connected or have multiple boundary components. Besides the theoretical analysis of the methods, the dissertation provides various numerical results in two and three dimensions that illustrate and support the theory.

Thesis (Ph. D.)--University of Texas at Austin, 2001. / Vita. Includes bibliographical references. Available also from UMI/Dissertation Abstracts International.

In preparation for, and for decision support during, CBRN (chemical, biological, radiological and nuclear) emergencies it is essential to know how such an event would turn out, so that one can prepare a possible evacuation. Afterwards it might be good to know how to backtrack and see what caused the emergency, and in the case of e.g. a gas leak, where did it begin? The Swedish Defence Research Agency (FOI) develops models for such scenarios. In this thesis FOI's model, "The Nordic Urban Dispersion model" (NUD), has been studied. The system of equations set up by this model was originally solved using Intel's PARDISO solver, which is a direct solver. An evaluation on how an iterative multigrid method would work to solve the system has been done in this thesis. The wind model is a mass-consistent model which sets up a diagnostic initial wind field. The final wind field is later minimized under the constraint of the continuity equation. The minimization problem is solved using Lagrange multipliers and the system turns into a Poisson-like problem. The iterative algebraic multigrid solver (AMG) which has been evaluated had difficulties solving the problem of an asymmetric system matrix generated by NUD. The AMG solver was then tried on a symmetric discrete Poisson problem instead, and the solution turns out to be the same as for the PARDISO solver. A comparison was made between the AMG and PARDISO solver, and for the discrete Poisson case the AMG solver turned out on top for both larger system size and less computational time. To try out the solvers for the original NUD case a modification of the boundary conditions was made to make the system matrix symmetric. This modification turns the problem into a mathematical problem rather than a physical one, as the wind fields generated are not physically correct. For this modified case both the solvers get the same solution in essentially the same computational time. A method of how to in the future solve the original (asymmetric) problem, by modifying the discretization of the boundary conditions, has been discussed.

Not available / text