This master thesis studies GPU-enabled parallel implementations of the 3D Parallel Marching Method (PMM). 3D PMM is aimed at solving the non-linear static Jacobi-Hamilton equations, which has real world applications such as in the study of geological foldings, where each layer of the Earth’s crust is considered as a front propagating over time. Using the parallel computer architectures, fast simulationscan be achieved, leading to less time consumption, quicker understanding of the inner Earth and enables early exploration of oil and gas reserves. Currently 3D PMM is implemented in shared memory architecture using OpenMP Application Programming Interface (API) and the MINT programming model, which translates C code into Compute Unified Device Architecture (CUDA) code for a single Graphical Process Unit (GPU). Parallel architectures have seen rapid growth in recent years, especially GPUs, allowing us to do faster simulations. In this thesis work, a new parallel implementation for 3D PMM has been done to exploit multicore CPU architectures as well as single and multiple GPUs. In a multiple GPU implementation, 3D data isdecomposed into 1D data for each GPU. CUDA streams are used to overlap the computation and communication within the single GPU. Part of the decomposed 3D volume data is kept in the respective GPU to avoid complete data transfer between the GPUs over a number of iterations. In total, there are two kinds of datatransfers that are involved while doing computation in the multiple GPUs: boundary value data transfer and decomposed 3D volume data transfer. The decomposed 3D volume data transfer is optimized between the multiple GPUs by using the peer to peer memory transfer in CUDA. The speedup is shown and compared between shared memory CPUs (E5-2660, 16cores), single GPU (GTX-590, C2050 and K20m) and multiple GPUs. Hand coded CUDA has shown slightly better performance than the Mint translated CUDA, and the multiple GPU implementation showed promising speedup compared to shared memory multicore CPUs and single GPU implementations.

In this thesis, the plausibility of developing a portable light-weight artillery computer has been investigated. The main goal of the project has been to replace the traditional methods that the Swedish Armed Forces are using today to find firing solutions for their mortar, the GRK m/84. A computational core has been written in Java that simulates the trajectory of a shell using the model in NATO's STANAG 4355. The developed system finds firing solutions by using shooting methods and the multi-dimensional Newton Raphson's method. A Graphical User Interface (GUI) tailored to mobile computers has been designed in Android. The computational core along with the GUI has been installed on a rugged hand held computer and the whole unit has been tested at Markstridsskolan (MSS). The tests showed that the computational core delivers firing solutions that coincide very well with the actual firing solutions needed to hit the desired target.

There are situations where you would like to know the size of an object but do not have a ruler nearby. However, it is likely that you are carrying a smartphone that has an integrated digital camera, so imagine if you could snap a photo of the object to get a size estimation. Different methods for finding the dimensions of a cuboid from a photography are evaluated in this project. A simple Android application implementing these methods has also been created. To be able to perform measurements of objects in images we need to know how the scene is reproduced by the camera. This depends on the traits of the camera, called the intrinsic parameters. These parameters are unknown unless a camera calibration is performed, which is a non-trivial task. Because of this eight smartphone cameras, of different models, were calibrated in search of similarities that could give ground for generalisations. To be able to determine the size of the cuboid the scale needs to be known, which is why a reference object is used. In this project a credit card is used as reference, which is placed on top of the cuboid. The four corners of the reference as well as four corners of the cuboid are used to determine the dimensions of the cuboid. Two methods, one dependent and one independent of the intrinsic parameters, are used to find the width and length, i.e. the sizes of the two dimensions that share a plane with the reference. These results are then used in another two methods to find the height of the cuboid. Errors were purposely introduced to the corners to investigate the performance of the different methods. The results show that the different methods perform very well and are all equally suitable for this type of problem. They also show that having correct reference corners is more important than having correct object corners as the results were highly dependent on the accuracy of the reference corners. Another conclusion is that the camera calibration is not necessary because different approximations of the intrinsic parameters can be used instead. / Det finns tillfällen då man undrar över storleken på ett föremål, men inte har något mätinstrument i närheten. Det är dock troligt att du har en smartphone på dig. Smartphones har oftast en integrerad digitalkamera, så tänk om du kunde ta ett foto på föremålet och få en storleksuppskattning. I det här projektet har olika metoder för att beräkna dimensionerna på ett rätblock utvärderats. En enkel Android-applikation som implementerar dessa metoder har också skapats. För att kunna göra mätningar på föremål i bilder måste vi veta hur vyn återskapas av kameran. Detta beror på kamerans egenskaper vilka kallas kameraparametrarna. Dessa parametrar kan man få fram genom att göra en kamerakalibrering, vilket inte är en trivial uppgift. Därför har åtta smartphonekameror, från olika tillverkare, kalibrerats för att se om det finns likheter mellan kamerorna som kan befoga vissa generaliseringar. För att kunna räkna ut storleken på rätblocket måste skalan vara känd och därför används ett referensobjekt. I detta projekt har ett kreditkort använts som referensobjekt. Referensen placeras ovanpå rätblocket och sedan används fyra av referensens hörn samt fyra av rätblockets hörn i beräkningarna. Två metoder, en beroende och en oberoende av kameraparametrarna, har använts för att beräkna längden och bredden, alltså längden på de två sidor som ligger i samma plan som referensobjektet. Detta resultat används sedan i ytterligare två olika metoder för att beräkna höjden på rätblocket. För att undersöka hur de olika metoderna klarade av fel manipulerades hörnen. Resultaten visar att de olika metoderna fungerar bra och är alla lika lämpliga för att lösa den här uppgiften. De visar också på att det är viktigare att referensobjektets hörn är korrekta än rätblockets hörn eftersom referensobjektets hörn hade större inverkan på resultaten. En slutsats som också kan dras är att kameraparametrarna kan approximeras och att kamerakalibrering därför inte nödvändigtvis behöver utföras.

In this work, prestressed elasticity problem as a model of the so-called glacial isostatic adjustment (GIA) process is studied. The model problem is described by a set of partial differential equations (PDE) and discretized with a mixed finite element (FE) formulation. In the presence of prestress the so-constructed system of equations is non-symmetric and indefinite. Moreover, the resulting system of equations is of the saddle point form. We focus on a robust and efficient block lower-triangular preconditioning method, where the lower diagonal block is and approximation of the so-called Schur complement. The Schur complement is approximated by the so-called element-wise Schur complement. The element-wise Schur complement is constructed by assembling exact local Schur complements on the cell elements and distributing the resulting local matrices to the global preconditioner matrix. We analyse the properties of the element-wise Schur complement for the symmetric indefinite system matrix and provide proof of its quality. We show that the spectral radius of the element-wise Schur complement is bounded by the exact Schur complement and that the quality of the approximation is not affected by the domain shape. The diagonal blocks of the lower-triangular preconditioner are combined with inner iterative schemes accelerated by (numerically) optimal and robust algebraic multigrid (AMG) preconditioner. We observe that on distributed memory systems, the top pivot block of the preconditioner is not scaling satisfactorily. The implementation of the methods is further studied using a general profiling tool, designed for clusters. For nonsymmetric matrices we use the theory of Generalized Locally Toeplitz (GLT) matrices and show the spectral behavior of the element-wise Schur complement, compared to the exact Schur complement. Moreover, we use the properties of the GLT matrices to construct a more efficient AMG preconditioner. Numerical experiments show that the so-constructed methods are robust and optimal.

Moving contact line problems appear in many natural and industrial processes. A contact line is formed where the interface between two immiscible fluids meets a solid wall. Examples from everyday life include raindrops falling on a window and water bugs resting on water surfaces. In many cases the dynamics of the contact line affects the overall behavior of the system. Industrial applications where the contact line behavior is important include gas and oil recovery in porous media, lubrication, inkjet printing and microfluidics. Computer simulations are fundamental tools to understand and predict the behavior.   In this thesis we look at numerical simulations of dynamic contact line problems. Despite their importance, the physics of moving contact lines is poorly understood. The standard Navier-Stokes equations together with the conventional no-slip boundary condition predicts a singularity in the shear stresses at the contact line. Atomistic processes at the contact line come into play, and it is necessary to include these processes in the model to resolve the singularity. In the case of capillary driven flows for example, it has been observed that the microscopic contact line dynamics has a large impact on the overall macroscopic flow. In Paper I we present a new multiscale model for numerical simulation of flow of two immiscible and incompressible fluids in the presence of moving contact points (i.e. two-dimensional problems). The paper presents a new boundary methodology based on combining a relation between the apparent contact angle and the contact point velocity, and a similarity solution for Stokes flow at a planar interface (the analytic Huh and Scriven velocity). The relation between the angle and the velocity is determined by performing separate microscopic simulations. The classical Huh and Scriven solution is only valid for flow over flat walls. In Paper II we use perturbation analysis to extend the solution to flow over curved walls. Paper III presents the parallel finite element solver that is used to perform the numerical experiments presented in this thesis. Finally, the new multiscale model (presented in Paper I) is applied to a relevant microfluidic research problem in Paper IV. For this problem it is very important to have a model that accurately takes the atomistic effects at contact lines into account.

To ensure a high level of safety and reliability of electronic/electric systems EMC (electromagnetic compatibility) tests together with computational techniques are used. In this thesis, mathematical modeling and computational electromagnetics are applied to mainly two case studies. In the first case study, electromagnetic modeling of electric networks and antenna structures above, and buried in, the ground are studied. The ground has been modelled either as a perfectly conducting or as a dielectric surface.  The second case study is focused on mathematical modeling and algorithms to solve the direct and inverse electromagnetic scattering problem for providing a model-based illustration technique. This electromagnetic scattering formulation is applied to describe a microwave imaging system called Breast Phantom. The final goal is to simulate and detect cancerous tissues in the human female breast by this microwave technique.   The common issue in both case studies has been the long computational time required for solving large systems of equations numerically. This problem has been dealt with using approximation methods, numerical analysis, and also parallel processing of numerical data. For the first case study in this thesis, Maxwell’s equations are solved for antenna structures and electronic networks by approximation methods and parallelized algorithms implemented in a LAN (Local Area Network). In addition, PMM (Point-Matching Method) has been used for the cases where the ground is assumed to act like a dielectric surface. For the second case study, FDTD (Finite-Difference Time Domain) method is applied for solving the electromagnetic scattering problem in two dimensions. The parallelized numerical FDTD-algorithm is implemented in both Central Processing Units (CPUs) and Graphics Processing Units (GPUs). / För att säkerställa människors säkerhet och tillförlitligheten hos elektriska/elektroniska system används EMC (elektromagnetisk kompatibilitet)-tester i kombination med matematisk modellering. För att undersöka biologiska vävnaders egenskaper används så kallade elektromagnetiska spridningsmetoder vid sidan om elektromagnetisk modellering. I denna avhandling har matematisk modellering och beräkningsmetoder använts för huvudsakligen två fallstudier. Den första fallstudien handlar om att analysera antennstrukturer och elektriska nät ovanför, och nergrävda i marken. Marken har modellerats antingen som en elektriskt ledande yta eller en dielektrisk yta. Den andra fallstudien fokuserar på matematisk modellering och algoritmer för att lösa ett elektromagnetiskt spridningsproblem för att beskriva en modellbaserad illustrationsteknik. Spridningsformuleringen tillämpas för att modellera ett avbildningssystem som använder mikrovågor, kallat Bröstfantomen. Det slutliga målet är att upptäcka cancervävnader i kvinnobröst genom denna mikrovågsteknik. Flaskhalsen i de båda fallstudierna har visat sig vara de långa beräkningstider som krävs för att lösa stora numeriska system. För att lösa problemet har approximationsmetoder, numerisk analys och även parallella beräkningar genomförts i detta arbete. För den första fallstudien har Maxwells ekvationer lösts genom CEM (Complex Image Methods) och med parallellisering i ett LAN (Local Area Network). I de fall där marken betraktas som en dielektrisk yta, har PMM (Point-Matching Method) tillämpats. I samband med den andra fallstudien har FDTD (Finite-Difference Time Domain) metoder tillämpats för att lösa ett elektromagnetiskt spridningsproblem i två dimensioner. En parallelliserad FDTD-algoritm har implementerats i både CPU:s (Central Processing Units) och GPU:s (Graphics Processing Units). / RALF3

In this thesis, we use finite difference operators with the Summation-By-Partsproperty (SBP) and a weak boundary treatment, known as SimultaneousApproximation Terms (SAT), to construct high-order accurate numerical schemes.The SBP property and the SAT’s makes the schemes provably stable. The numerical procedure is general, and can be applied to most problems, but we focus on hyperbolic problems such as the shallow water, Euler and wave equations. For a well-posed problem and a stable numerical scheme, data must be available at the boundaries of the domain. However, there are many scenarios where additional information is available inside the computational domain. In termsof well-posedness and stability, the additional information is redundant, but it can still be used to improve the performance of the numerical scheme. As a first contribution, we introduce a procedure for implementing additional data using SAT’s; we call the procedure the Multiple Penalty Technique (MPT). A stable and accurate scheme augmented with the MPT remains stable and accurate. Moreover, the MPT introduces free parameters that can be used to increase the accuracy, construct absorbing boundary layers, increase the rate of convergence and control the error growth in time. To model infinite physical domains, one need transparent artificial boundary conditions, often referred to as Non-Reflecting Boundary Conditions (NRBC). In general, constructing and implementing such boundary conditions is a difficult task that often requires various approximations of the frequency and range of incident angles of the incoming waves. In the second contribution of this thesis,we show how to construct NRBC’s by using SBP operators in time. In the final contribution of this thesis, we investigate long time error bounds for the wave equation on second order form. Upper bounds for the spatial and temporal derivatives of the error can be obtained, but not for the actual error. The theoretical results indicate that the error grows linearly in time. However, the numerical experiments show that the error is in fact bounded, and consequently that the derived error bounds are probably suboptimal.

In this thesis we consider errors arising from finite difference operators on summation-by-parts (SBP) form, used in the discretisation of partial differential equations. The SBP operators are augmented with simultaneous-approximation-terms (SATs) to weakly impose boundary conditions. The SBP-SAT framework combines high order of accuracy with a systematic construction of provably stable boundary procedures, which renders it suitable for a wide range of problems. The first part of the thesis treats wave propagation problems discretised using SBP operators on coarse grids. Unless special care is taken, inaccurate approximations of the underlying dispersion relation materialises in the form of an incorrect propagation speed. We present a procedure for constructing SBP operators with minimal dispersion error. Experiments indicate that they outperform higher order non-optimal SBP operators for flow problems involving high frequencies and long simulation times. In the second part of the thesis, the formal order of accuracy of SBP operators near boundaries is analysed. We prove that the order in the interior of a diagonal norm based SBP operator must be at least twice that of the boundary stencil, irrespective of the grid point distribution near the boundary. This generalises the classical theory posed on uniform and conforming grids. We further show that for a common class of SBP operators, the diagonal norm defines a quadrature rule of the same order as the interior stencil. Again, this result is independent of the grid. In the final contribution if the thesis, we introduce the notion of a transmission problem to describe a general class of problems where different dynamics are coupled in time. Well-posedness and stability analyses are performed for continuous and discrete problems. A general condition is obtained that is necessary and sufficient for the transmission problem to satisfy an energy estimate. The theory provides insights into the coupling of fluid flow models, multi-block formulations, numerical filters, interpolation and multi-grid implementations.

In this thesis, techniques for efficient utilization of modern computer hardwarefor numerical simulation are considered. In particular, we study techniques for improving the performance of computations using the finite element method. One of the main difficulties in finite-element computations is how to perform the assembly of the system matrix efficiently in parallel, due to its complicated memory access pattern. The challenge lies in the fact that many entries of the matrix are being updated concurrently by several parallel threads. We consider transactional memory, an exotic hardware feature for concurrent update of shared variables, and conduct benchmarks on a prototype multicore processor supporting it. Our experiments show that transactions can both simplify programming and provide good performance for concurrent updates of floating point data. Secondly, we study a matrix-free approach to finite-element computation which avoids the matrix assembly. In addition to removing the need to store the system matrix, matrix-free methods are attractive due to their low memory footprint and therefore better match the architecture of modern processors where memory bandwidth is scarce and compute power is abundant. Motivated by this, we consider matrix-free implementations of high-order finite-element methods for execution on graphics processors, which have seen a revolutionary increase in usage for numerical computations during recent years due to their more efficient architecture. In the implementation, we exploit sum-factorization techniques for efficient evaluation of matrix-vector products, mesh coloring and atomic updates for concurrent updates, and a geometric multigrid algorithm for efficient preconditioning of iterative solvers. Our performance studies show that on the GPU, a matrix-free approach is the method of choice for elements of order two and higher, yielding both a significantly faster execution, and allowing for solution of considerably larger problems. Compared to corresponding CPU implementations executed on comparable multicore processors, the GPU implementation is about twice as fast, suggesting that graphics processors are about twice as power efficient as multicores for computations of this kind.

This thesis focuses on computationally efficient methods for flow in fractured porous media. Two approaches are presented where the interface is embedded on the underlying finite element mesh. The methods allow for representation of the interface geometry from the underlying discretization and with discontinuities across the interface. However, embedding interfaces raises stability concerns in which we alleviate using stabilization terms. The aim of this thesis is to present the basics of the two main approaches and to provide brief details on the mathematics involved. / Denna avhandling fokuserar på effektiva beräkningsmetoder för flöde i porösa media med sprickor. Två tillvägagångssätt presenteras där sprickan tillåts skära det underliggande finita elementnätet. Sprickans inverkan på flödet tas om hand med hjälp av den underliggande diskretiseringen som tillåter diskontinuiteter. Med andra ord kan flöden modelleras med olika egenskaper; på var sida av sprickan, samt längs sprickan. Metoden tar även hand om instabilitet som uppstår dels på grund av godtyckliga skärningar av bakgrundselementen och dels på grund av olika materialegenskaper. Syftet med denna avhandling är att presentera grunderna för dessa metoder och ge grundläggande matematiska förklaringar.