## Modular Arithmetic for Solving Linear Equations on the GPU

Faculty of Information Technology, Czech Technical University, Prague

Technical University of Liberec, 2012

@inproceedings{hladik2012modular,

author={Hladik, J. and Simecek, 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},

language={English},

url={http://shimi.webzdarma.cz/vyzkum/sna12/download.pdf}

}

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 [2] to solve dense systems of linear equations precisely. The idea behind is sounds quite simple – bypass oating 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 [5] so we can expect a huge speedup compared to CPU implementations.

April 11, 2012 by hgpu