This repository hosts sample code implementing the Raghavendra-Fliege algorithm for solving linear systems.

Available code

The code is grouped into directories according to the implementation language. All example programs run two tests in sequence: solve a linear system Ax = b with A the identiy matrix, and solve a linear system where A is a random matrix with coefficients drawn uniformly from an interval.

References

• The original draft paper by Raghavendra describing the new solver for linear systems on finite fields: http://www.eecs.berkeley.edu/~prasad/linsystems.pdf

• R. J. Lipton's blog post discussing Raghavendra's algorithm: http://rjlipton.wordpress.com/2012/08/09/a-new-way-to-solve-linear-equations/

• The arXiv paper by J. Fliege providing a modified version of the algorithm that works over the reals: http://arxiv.org/pdf/1209.3995v1