The Krawczyk Algorithm: Rigorous Bounds for Linear Equation Solution on an FPGA

In the majority of scientific computing applications, values are represented using a floating point number system. However, this number system only considers an approximate value without any indication of the approximation's accuracy. Interval arithmetic provides a means to ensure that the solution is bounded with absolute certainty. However, whilst interval arithmetic can be applied to any algorithm to ensure bounds on a solution, the limitations of interval arithmetic can lead to bounds that are not always tight and hence not particularly useful. As a result, some algorithms are specifically designed with interval arithmetic in mind to find high quality bounds on a solution; the Krawczyk algorithm is one such algorithm. The Krawczyk algorithm is targeted towards solving systems of linear equations, which is a common problem in scientific computing and has drawn a wide interest in the FPGA community. We show that by accelerating this algorithm in hardware, developing specialised arithmetic units, it is possible to gain orders of magnitude improvement in execution time over a C implementation.