Summary at: [1] http://rjlipton.wordpress.com/2012/08/09/a-new-way-to-solve-linear-equations/

Original paper by Prasad Raghavendra at: [2] http://www.eecs.berkeley.edu/~prasad/linsystems.pdf

This is to solve a linear equation system over a finite field . The finite field is has a finite size of (a prime), we can think of it as integers 0 to , with the addition and multiplication are done in modulus . Matrix is of order .

The algorithm to solve the problem is as follows: It first takes random vectors from , make it into a set . Then filter to find those who can satisfy the first row of . The satisfying random vectors are then “recombined”: Select of them randomly and sum up to give a new vector. Repeat this random select and sum up process to produce vectors. These vectors are make into a set , then applied to the second row of . The filtered set at the last row are the solutions for the linear equation.

Note that, in the finite field, there could be infinitely many solutions for a linear system. Therefore a set of solutions is produced. The original paper [2] gives the analysis on the size of required and the performance bound.

Bibliographic data

@misc{
   title = "A Randomized Algorithm for Linear Equations over Prime Fields",
   author = "Prasad Raghavendra",
   month = "Aug",
   year = "2012",
}