Clock Math — a System for Solving SLEs Exactly

Authors

  • Jakub Hladík
  • Róbert Lórencz
  • Ivan Šimeček

DOI:

https://doi.org/10.14311/1795

Keywords:

integer arithmetic, modular arithmetic, Hilbert’s matrix, error-free, GPGPU, solver, OpenCL, optimizations.

Abstract

In this paper, we present a GPU-accelerated hybrid system that solves ill-conditioned systems of linear equations exactly. Exactly means without rounding errors due to using integer arithmetics. First, we scale floating-point numbers up to integers, then we solve dozens of SLEs within different modular arithmetics and then we assemble sub-solutions back using the Chinese remainder theorem. This approach effectively bypasses current CPU floating-point limitations. The system is capable of solving Hilbert’s matrix without losing a single bit of precision, and with a significant speedup compared to existing CPU solvers.

Downloads

Download data is not yet available.

Author Biographies

Jakub Hladík

Róbert Lórencz

Ivan Šimeček

Downloads

Published

2013-01-02

Issue

Section

Articles