Low latency and division free Gauss-Jordan solver in floating point arithmetic

In many applications, the solution of a linear system is computed with Gaussian elimination followed by back-substitution, or Gauss-Jordan elimination. The latter is intrinsically more parallel, enabling smaller computing latencies at the price of more complex hardware. However both methods require the division operator, which leads to a time-consuming resource in the critical path of the algorithms and impacts the global processing's latency. Jordan was already aware of a division free algorithm. However, its implementation involves multiplications at each step and the size of the numbers rapidly becomes too big for an efficient implementation of large systems. In this work, we present a small modification to the division free algorithm in order to keep the size of the numbers in a reasonable range for standard floating point numbers. This is possible thanks to the special format of floating point numbers, which enables error free and hardware efficient divisions by powers of two. We also propose a parallel and pipelined architecture that best exploits the proposed algorithm, including partial pivoting. We specially focus on the global latency of the system as a function of its size, the latency of the floating point operators, and the number of operators that are available. Results demonstrate that current FPGAs can solve linear systems larger than hundred equations within ten microseconds. This represents a two order of magnitude improvement over previous implementations for relatively small systems.