Description
When solving a sparse system of linear equations Ax = b for x by means of iterative methods, the convergence can be improved considerably by formally multiplying the system with a matrix B that is a good approximation to the inverse of A. One possibility is to construct an approximate sparse inverse B by minimizing ||AB - Id|| for a certain sparsity pattern of B, where Id denotes the identity matrix.
The task is to implement a sparse approximate inverse preconditioner in ViennaCL using OpenCL. Since such a preconditioner can be computed in parallel, it is an ideal candidate for GPUs and multi-core CPUs.
Benefit for the Student
The student will appreciate the importance of efficient parallel preconditioners. Moreover, (s)he will learn how to use current multi-core hardware efficiently for linear algebra computations.
Benefit for the Project
In contrast to dense linear algebra, for which a number of GPU implementations is available, sparse linear algebra is often ignored in other libraries. ViennaCL will be the first general-purpose linear algebra library to support a non-trivial parallel preconditioner.
Requirements
The student should be familiar with basic linear algebra, i.e. matrices and vectors in general and QR-decompositions in particular. Moderate C and C++ knowledge is sufficient. Background in OpenCL (or CUDA) is of advantage. Access to a machine with a mid- to high-range graphics adapter is beneficial, but not mandatory.