Sparse linear algebra on a GPU: with Applications to flow in porous Media

We investigate what the graphics processing units (GPUs) have to offer compared to the central processing units (CPUs) when solving a sparse linear system of equations. This is performed by using a GPU to simulate fluid-flow in a porous medium. Flow-problems are discretized mainly by the mimetic finite element discretization, but also by a two-point flux-approximation (TPFA) method. Both of these discretization schemes are explained in detail. Example-models of flow in porous media are simulated, as well as CO2 -injection into a realistic model of a sub-sea storage-cite. The linear algebra is solved by the conjugate gradient (CG) method without a preconditioner. The computationally most expensive calculation of this algorithm is the matrix-vector product. Several formats for storing sparse matrices are presented and implemented on both a CPU and a GPU. The fastest format on the CPU is different from the format performing best on the GPU. Implementations for the GPU is written for the compute unified driver architecture (CUDA), and C++ is used for the CPU-implementations. The program is created as a plug-in for Matlab and may be used to solve any symmetric positive definite (SPD) linear system. How a GPU differs from a CPU is explained, where focus is put on how a program should be written to fully utilize the potential of a GPU. The optimized implementation on the GPU outperforms the CPU, and offers a substantial improvement compared to Matlab s conjugate gradient method, when no preconditioner is used