Scientists' ability to generate and store simulation results is outpacing their ability to analyze them via ad hoc programs. We observe that these programs exhibit an algebraic structure that can be used to facilitate reasoning and improve performance. In this dissertation, we present a formal data model that exposes this algebraic structure, then implement the model, evaluate it, and use it to express, optimize, and reason about data transformations in a variety of scientific domains. Simulation results are defined over a logical grid structure that allows a continuous domain to be represented discretely in the computer. Existing approaches for manipulating these gridded datasets are incomplete. The performance of SQL queries that manipulate large numeric datasets is not competitive with that of specialized tools, and the up-front effort required to deploy a relational database makes them unpopular for dynamic scientific applications. Tools for processing multidimensional arrays can only capture regular, rectilinear grids. Visualization libraries accommodate arbitrary grids, but no algebra has been developed to simplify their use and afford optimization. Further, these libraries are data dependent—physical changes to data characteristics break user programs. We adopt the grid as a first-class citizen, separating topology from geometry and separating structure from data. Our model is agnostic with respect to dimension, uniformly capturing, for example, particle trajectories (1-D), sea-surface temperatures (2-D), and blood flow in the heart (3-D). Equipped with data, a grid becomes a gridfield. We provide operators for constructing, transforming, and aggregating gridfields that admit algebraic laws useful for optimization. We implement the model by analyzing several candidate data structures and incorporating their best features. We then show how to deploy gridfields in practice by injecting the model as middleware between heterogeneous, ad hoc file formats and a popular visualization library. In this dissertation, we define, develop, implement, evaluate and deploy a model of gridded datasets that accommodates a variety of complex grid structures and a variety of complex data products. We evaluate the applicability and performance of the model using datasets from oceanography, seismology, and medicine and conclude that our model-driven approach offers significant advantages over the status quo.

Coarse grid projection (CGP) methodology is a novel multigrid method for systems involving decoupled nonlinear evolution equations and linear elliptic Poisson equations. The nonlinear equations are solved on a fine grid and the linear equations are solved on a corresponding coarsened grid. Mapping operators execute data transfer between the grids. The CGP framework is constructed upon spatial and temporal discretization schemes. This framework has been established for finite volume/difference discretizations as well as explicit time integration methods. In this article we present for the first time a version of CGP for finite element discretizations, which uses a semi-implicit time integration scheme. The mapping functions correspond to the finite-element shape functions. With the novel data structure introduced, the mapping computational cost becomes insignificant. We apply CGP to pressure correction schemes used for the incompressible Navier Stokes flow computations. This version is validated on standard test cases with realistic boundary conditions using unstructured triangular meshes. We also pioneer investigations of the effects of CGP on the accuracy of the pressure field. It is found that although CGP reduces the pressure field accuracy, it preserves the accuracy of the pressure gradient and thus the velocity field, while achieving speedup factors ranging from approximately 2 to 30. Exploring the influence of boundary conditions on CGP, the minimum speedup occurs for velocity Dirichlet boundary conditions, while the maximum speedup occurs for open boundary conditions. We discuss the CGP method as a guide for partial mesh refinement of incompressible flow computations and show its application for simulations of flow over a backward facing step and flow past a cylinder. / Master of Science / Coarse Grid Projection (CGP) methodology is a new multigrid technique applicable to pressure projection methods for solving the incompressible Navier-Stokes equations. In the CGP approach, the nonlinear momentum equation is evolved on a fine grid, and the linear pressure Poisson equation is solved on a corresponding coarsened grid. Mapping operators transfer the data between the grids. Hence, one can save a considerable amount of CPU time due to reducing the resolution of the pressure filed while maintaining excellent to reasonable accuracy, depending on the level of coarsening.

O foco principal do presente trabalho é estender uma metodologia numérica embasada no uso de uma técnica de refinamento adaptativo de malha (AMR - Adaptive Mesh Refinement) e no uso de esquemas temporais multipasso implícitos-explícitos (IMEX) a aplicações envolvendo escoamentos reativos com baixo número de Mach. Originalmente desenvolvida para escoamentos incompressíveis, a formulação euleriana daquela metodologia emprega as equações de Navier-Stokes como modelo matemático para descrever a dinâmica do escoamento e o Método da Projeção, baseado no divergente nulo da velocidade do escoamento, para tratar o acoplamento pressão-velocidade presente na formulação com variáveis primitivas. Tal formulação euleriana original é estendida para acomodar novas equações agregadas ao modelo matemático da fase contínua: conservação de massa, fração de mistura (para representar as concentrações de combustível e oxidante), e energia. Além disso, uma equação termodinâmica de estado é integrada ao modelo matemático estendido e é empregada juntamente com a equação de conservação de massa para produzir uma nova restrição (não nula desta vez) ao divergente do campo de velocidade. Assume-se que o escoamento ocorre a baixo número de Mach (hipótese principal). O Método de Diferença Finita é empregado na discretização espacial das variáveis eulerianas de estado, empregando-se uma malha AMR. As vantagens e dificuldades desta extensão são cuidadosamente investigadas e reportadas. Pela importância, do ponto de vista de aplicações práticas, alguns estudos numéricos preliminares envolvendo escoamentos incompressíveis turbulentos com sprays são realizados (as gotículas compõem a fase dispersa). Num primeiro momento, apenas sprays com gotículas inertes são considerados. Embora ainda apenas iniciais, tais estudos já se mostram importantes pois identificam com clareza, em primeira instância, algumas das dificuldades inerentes a serem enfrentadas ao se tratar dentro desta nova metodologia um conjunto relativamente grande de gotículas lagrangianas. No caso de escoamentos incompressíveis turbulentos com sprays, a integração temporal se dá com métodos IMEX para a fase contínua e com o Método de Euler Modificado para a fase dispersa. A turbulência, em todos os casos que a envolvem, é tratada pelo modelo de Simulação das Grandes Escalas (LES - Large Eddy Simulation). As simulações computacionais se dão em um domínio tridimensional, um parelelepípedo, e empregam uma extensão (resultante do presente trabalho) do código AMR3D, um programa de computador sequencial implementado em Fortran90, oriundo de uma colaboração de longa data entre o IME-USP e o MFLab/FEMEC-UFU (Laboratório de Dinâmica de Fluidos da Universidade Federal de Uberlândia). O processamento foi efetuado no LabMAP (Laboratório da Matemática Aplicada do IME-USP). / It is the main goal of the present work to extend a numerical methodology based on both the use of an adaptive mesh refinement technique (AMR) and the use of a multistep, implicit-explicit time-step strategy (IMEX) to applications involving low Mach number reactive flows. Originally developed for incompressible flows, the Eulerian formulation of that methodology employs the Navier-Stokes equations to model the flow dynamics and the Projection Method, based on the vanishing divergence of the velocity field, to tackle the pressure-velocity coupling present when using primitive variables. That Eulerian formulation is extended by adding a new set of equations to the original mathematical model, describing the various properties of the continuous phase: mass conservation, mixture fraction (to represent concentrations of fuel and oxidizer) and energy. Also, a thermodynamic equation of state is included into the extended mathematical model which is employed, along with the equation for the conservation of mass, to derive a new restriction (this time, different from zero) to the divergence of the velocity field. It is assumed that one is dealing with a low Mach number flow (the main hipothesis). The discretization in space employs the Finite Difference Method for the Eulerian variables on a AMR mesh. Advantages and difficulties of such an extension of the previous methodology are carefully investigated and reported. For its importance in the real-world applications, few preliminary numerical studies involving incompressible turbulent flows with sprays are performed (the droplets form what it is called the dispersed phase). Only sprays formed by inert droplets are considered. Even though initial yet, such studies are most important because they clearly identify, first hand, certain difficulties in handling relatively large sets of Lagrangian droplets in the context of this new AMR methodology. In the context of turbulent incompressible flows with sprays, the overall time-step scheme is given by IMEX methods for the continuous phase and by the Improved Euler Method for the dispersed phase. In all the cases in which it is considered, turbulence is modeled by the Large Eddy Simulation (LES) model. The computational simulations are held in a tridimensional domain given by a paralellepiped and all of them employ the extention (resulting of the present work) of the AMR3D code, a sequencial computer program implemented in Fortran90, whose origin is the collaborative work between IMEUSP and MFLab/FEMEC-UFU (Fluid Dynamics Laboratory, Federal University of Uberlândia). Computations were performed at LabMAP (Applied Mathematics Laboratory at IME-USP).

Dans cette thèse, nous proposons des algorithmes et présentons des résultats numériques pour la résolution de jeux répétés stochastiques, à deux joueurs et somme nulle dont l'espace d'état est de grande taille. En particulier, nous considérons la classe de jeux en information complète et en horizon infini. Dans cette classe, nous distinguons d'une part le cas des jeux avec gain actualisé et d'autre part le cas des jeux avec gain moyen. Nos algorithmes, implémentés en C, sont principalement basés sur des algorithmes de type itérations sur les politiques et des méthodes multigrilles. Ces algorithmes sont appliqués soit à des équations de la programmation dynamique provenant de problèmes de jeux à deux joueurs à espace d'états fini, soit à des discrétisations d'équations de type Isaacs associées à des jeux stochastiques différentiels. Dans la première partie de cette thèse, nous proposons un algorithme qui combine l'algorithme des itérations sur les politiques pour les jeux avec gain actualisé à des méthodes de multigrilles algébriques utilisées pour la résolution des systèmes linéaires. Nous présentons des résultats numériques pour des équations d'Isaacs et des inéquations variationnelles. Nous présentons également un algorithme d'itérations sur les politiques avec raffinement de grilles dans le style de la méthode FMG. Des exemples sur des inéquations variationnelles montrent que cet algorithme améliore de façon non négligeable le temps de résolution de ces inéquations. Pour le cas des jeux avec gain moyen, nous proposons un algorithme d'itération sur les politiques pour les jeux à deux joueurs avec espaces d'états et d'actions finis, dans le cas général multichaine (c'est-à-dire sans hypothèse d'irréductibilité sur les chaînes de Markov associées aux stratégies des deux joueurs). Cet algorithme utilise une idée développée dans Cochet-Terrasson et Gaubert (2006). Cet algorithme est basé sur la notion de projecteur spectral non-linéaire d'opérateurs de la programmation dynamique de jeux à un joueur (lequel est monotone et convexe). Nous montrons que la suite des valeurs et valeurs relatives satisfont une propriété de monotonie lexicographique qui implique que l'algorithme termine en temps fini. Nous présentons des résultats numériques pour des jeux discrets provenant d'une variante des jeux de Richman et sur des problèmes de jeux de poursuite. Finalement, nous présentons de nouveaux algorithmes de multigrilles algébriques pour la résolution de systèmes linéaires singuliers particuliers. Ceux-ci apparaissent, par exemple, dans l'algorithme d'itérations sur les politiques pour les jeux stochastiques à deux joueurs et somme nulle avec gain moyen, décrit ci-dessus. Nous introduisons également une nouvelle méthode pour la recherche de mesures invariantes de chaînes de Markov irréductibles basée sur une approche de contrôle stochastique. Nous présentons un algorithme qui combine les itérations sur les politiques d'Howard et des itérations de multigrilles algébriques pour les systèmes linéaires singuliers.

University of Macau / Faculty of Science and Technology / Department of Mathematics

We propose multigrid methods for solving Hamilton-Jacobi-Bellman (HJB) and Hamilton-Jacobi-Bellman-Isaacs (HJBI) equations. The methods are based on the full approximation scheme. We propose a damped-relaxation method as smoother for multigrid. In contrast with policy iteration, the relaxation scheme is convergent for both HJB and HJBI equations. We show by local Fourier analysis that the damped-relaxation smoother effectively reduces high frequency error. For problems where the control has jumps, restriction and interpolation methods are devised to capture the jump on the coarse grid as well as during coarse grid correction. We will demonstrate the effectiveness of the proposed multigrid methods for solving HJB and HJBI equations arising from option pricing as well as problems where policy iteration does not converge or converges slowly.

Nuclear reactor design requires the calculation of integral core parameters and power and radiation profiles. These physical parameters are obtained by the solution of the linear neutron transport equation over the geometry of the reactor. In order to represent the fine structure of the nuclear core a very small geometrical mesh size should be used, but the computational capacity available these days is still not enough to solve these transport problems in the time range (hours-days) that would make the method useful as a design tool. This problem is traditionally solved by the solution of simple, smaller problems in specific parts of the core and then use a procedure known as homogenization to create average material properties and solve the full problem with a wider mesh size. The iterative multi-level solution procedure is inspired in this multi-stage approach, solving the problem at fuel-pin (cell) level, fuel assembly and nodal levels. The nested geometrical structure of the finite element representation of a reactor can be used to create a set of restriction/prolongation operators to connect the solution in the different levels. The procedure is to iterate between the levels, solving for the error in the coarse level using as source the restricted residual of the solution in the finer level. This way, the complete problem is only solved in the coarsest level and in the other levels only a pair of restriction/interpolation operations and a relaxation is required. In this work, a multigrid solver is developed for the in-moment equation of the spherical harmonics, finite element formulation of the second order transport equation. This solver is implemented as a subroutine in the code EVENT. Numerical tests are provided as a standalone diffusion solver and as part of a block Jacobi transport solver.

We propose multigrid methods for solving Hamilton-Jacobi-Bellman (HJB) and Hamilton-Jacobi-Bellman-Isaacs (HJBI) equations. The methods are based on the full approximation scheme. We propose a damped-relaxation method as smoother for multigrid. In contrast with policy iteration, the relaxation scheme is convergent for both HJB and HJBI equations. We show by local Fourier analysis that the damped-relaxation smoother effectively reduces high frequency error. For problems where the control has jumps, restriction and interpolation methods are devised to capture the jump on the coarse grid as well as during coarse grid correction. We will demonstrate the effectiveness of the proposed multigrid methods for solving HJB and HJBI equations arising from option pricing as well as problems where policy iteration does not converge or converges slowly.

Geometric Multigrid (GMG) methods are widely used in numerical analysis to accelerate the convergence of partial differential equations solvers using a hierarchy of grid discretizations. These solvers find plenty of applications in various fields in engineering and scientific domains, where solving PDEs is of fundamental importance. Using multigrid methods, the pace at which the solvers arrive at the solution can be improved at an algorithmic level. With the advance in modern computer architecture, solving problems with higher complexity and sizes is feasible - this is also the case with multigrid methods. However, since hardware support alone cannot achieve high performance in execution time, there is a need for good software that help programmers in doing so. Multiple grid sizes and recursive expression of multigrid cycles make the task of manual program optimization tedious and error-prone. A high-level language that aids domain experts to quickly express complex algorithms in a compact way using dedicated constructs for multigrid methods and with good optimization support is thus valuable. Typical computation patterns in a GMG algorithm includes stencils, point-wise accesses, restriction and interpolation of a grid. These computations can be optimized for performance on modern architectures using standard parallelization and locality enhancement techniques. Several past works have addressed the problem of automatic optimizations of computations in various scientific domains using a domain-specific language (DSL) approach. A DSL is a language with features to express domain-specific computations and compiler support to enable optimizations specific to these computations. Halide and PolyMage are two of the recent works in this direction, that aim to optimize image processing pipelines. Many computations like upsampling and downsampling an image are similar to interpolation and restriction in geometric multigrid methods. In this thesis, we demonstrate how high performance can be achieved on GMG algorithms written in the PolyMage domain-specific language with new optimizations we added to the compiler. We also discuss the implementation of non-trivial optimizations, on PolyMage compiler, necessary to achieve high parallel performance for multigrid methods on modern architectures. We realize these goals by: • introducing multigrid domain-specific constructs to minimize the verbosity of the algorithm specification; • storage remapping to reduce the memory footprint of the program and improve cache locality exploitation; • mitigating execution time spent in data handling operations like memory allocation and freeing, using a pool of memory, across multiple multigrid cycles; and • incorporating other well-known techniques to leverage performance, like exploiting multi-dimensional parallelism and minimizing the lifetime of storage buffers. We evaluate our optimizations on a modern multicore system using five different benchmarks varying in multigrid cycle structure, complexity and size, for two-and three-dimensional data grids. Experimental results show that our optimizations: • improve performance of existing PolyMage optimizer by 1.31x; • are better than straight-forward parallel and vector implementations by 3.2x; • are better than hand-optimized versions in conjunction with optimizations by Pluto, a state-of-the-art polyhedral source-to-source optimizer, by 1.23x; and • achieve up to 1.5$\times$ speedup over NAS MG benchmark from the NAS Parallel Benchmarks. (The speedup numbers are Geometric means over all benchmarks)

O foco principal do presente trabalho é estender uma metodologia numérica embasada no uso de uma técnica de refinamento adaptativo de malha (AMR - Adaptive Mesh Refinement) e no uso de esquemas temporais multipasso implícitos-explícitos (IMEX) a aplicações envolvendo escoamentos reativos com baixo número de Mach. Originalmente desenvolvida para escoamentos incompressíveis, a formulação euleriana daquela metodologia emprega as equações de Navier-Stokes como modelo matemático para descrever a dinâmica do escoamento e o Método da Projeção, baseado no divergente nulo da velocidade do escoamento, para tratar o acoplamento pressão-velocidade presente na formulação com variáveis primitivas. Tal formulação euleriana original é estendida para acomodar novas equações agregadas ao modelo matemático da fase contínua: conservação de massa, fração de mistura (para representar as concentrações de combustível e oxidante), e energia. Além disso, uma equação termodinâmica de estado é integrada ao modelo matemático estendido e é empregada juntamente com a equação de conservação de massa para produzir uma nova restrição (não nula desta vez) ao divergente do campo de velocidade. Assume-se que o escoamento ocorre a baixo número de Mach (hipótese principal). O Método de Diferença Finita é empregado na discretização espacial das variáveis eulerianas de estado, empregando-se uma malha AMR. As vantagens e dificuldades desta extensão são cuidadosamente investigadas e reportadas. Pela importância, do ponto de vista de aplicações práticas, alguns estudos numéricos preliminares envolvendo escoamentos incompressíveis turbulentos com sprays são realizados (as gotículas compõem a fase dispersa). Num primeiro momento, apenas sprays com gotículas inertes são considerados. Embora ainda apenas iniciais, tais estudos já se mostram importantes pois identificam com clareza, em primeira instância, algumas das dificuldades inerentes a serem enfrentadas ao se tratar dentro desta nova metodologia um conjunto relativamente grande de gotículas lagrangianas. No caso de escoamentos incompressíveis turbulentos com sprays, a integração temporal se dá com métodos IMEX para a fase contínua e com o Método de Euler Modificado para a fase dispersa. A turbulência, em todos os casos que a envolvem, é tratada pelo modelo de Simulação das Grandes Escalas (LES - Large Eddy Simulation). As simulações computacionais se dão em um domínio tridimensional, um parelelepípedo, e empregam uma extensão (resultante do presente trabalho) do código AMR3D, um programa de computador sequencial implementado em Fortran90, oriundo de uma colaboração de longa data entre o IME-USP e o MFLab/FEMEC-UFU (Laboratório de Dinâmica de Fluidos da Universidade Federal de Uberlândia). O processamento foi efetuado no LabMAP (Laboratório da Matemática Aplicada do IME-USP). / It is the main goal of the present work to extend a numerical methodology based on both the use of an adaptive mesh refinement technique (AMR) and the use of a multistep, implicit-explicit time-step strategy (IMEX) to applications involving low Mach number reactive flows. Originally developed for incompressible flows, the Eulerian formulation of that methodology employs the Navier-Stokes equations to model the flow dynamics and the Projection Method, based on the vanishing divergence of the velocity field, to tackle the pressure-velocity coupling present when using primitive variables. That Eulerian formulation is extended by adding a new set of equations to the original mathematical model, describing the various properties of the continuous phase: mass conservation, mixture fraction (to represent concentrations of fuel and oxidizer) and energy. Also, a thermodynamic equation of state is included into the extended mathematical model which is employed, along with the equation for the conservation of mass, to derive a new restriction (this time, different from zero) to the divergence of the velocity field. It is assumed that one is dealing with a low Mach number flow (the main hipothesis). The discretization in space employs the Finite Difference Method for the Eulerian variables on a AMR mesh. Advantages and difficulties of such an extension of the previous methodology are carefully investigated and reported. For its importance in the real-world applications, few preliminary numerical studies involving incompressible turbulent flows with sprays are performed (the droplets form what it is called the dispersed phase). Only sprays formed by inert droplets are considered. Even though initial yet, such studies are most important because they clearly identify, first hand, certain difficulties in handling relatively large sets of Lagrangian droplets in the context of this new AMR methodology. In the context of turbulent incompressible flows with sprays, the overall time-step scheme is given by IMEX methods for the continuous phase and by the Improved Euler Method for the dispersed phase. In all the cases in which it is considered, turbulence is modeled by the Large Eddy Simulation (LES) model. The computational simulations are held in a tridimensional domain given by a paralellepiped and all of them employ the extention (resulting of the present work) of the AMR3D code, a sequencial computer program implemented in Fortran90, whose origin is the collaborative work between IMEUSP and MFLab/FEMEC-UFU (Fluid Dynamics Laboratory, Federal University of Uberlândia). Computations were performed at LabMAP (Applied Mathematics Laboratory at IME-USP).