Modular Arithmetic for Solving Linear Equations on the GPU
Author: J. Hladík, Ivan Šimeček

GPGPU, modular arithmetic, solver of dense systems of linear equations


The linear algebraic equations solution is quite a frequent task within numerical mathematics. One might often find problems while solving problems of the ill-conditioned matrix. The solution stability cannot be ensured for large dense sets of linear equations. Rounding error during the numerical computation cannot be tolerated. There are methods developed that minimize the influence of rounding errors on the solution. The one method I am using relies on modular arithmetic \cite{gregory80} to solve dense systems of linear equations precisely. The idea behind is sounds quite simple -- bypass floating point rounding limitations using integer arithmetic. It consist of three parts -- converting floating point numbers into integers, solving system of linear equations and finally converting back. In this paper I propose a GPU-running system that solves systems of linear equations on the GPU. Modern GPU hardware is capable of accelerating data-parallel algorithms \cite{nvidiaprogramming} so we can expect a huge speedup compared to CPU implementations.


final version (in .PDF format)

BibTex entry:
author = {Hlad{\'\i}k, J. and {\v S}ime{\v c}ek, I.},
title = {Modular Arithmetic for Solving Linear Equations on the GPU},
booktitle = {{Seminar on Numerical Analysis}},
year = {2012},
pages = {68--70},
address = {Liberec},
publisher = {Technical University of Liberec},
isbn = {978-80-7372-821-2},
keywords = {sparse matrix, compression},
language = {English}