Best way to exactly solve a linear system (300x300) with integer coefficients I want to solve system of linear equations of size 300x300 (300 variables & 300 equations) exactly (not with floating point, aka dgesl, but with fractions in answer). All coefficients in this system are integer (e.g. 32 bit), there is only 1 solution to it. There are non-zero constant terms in right column (b).
A*x = b



*

*where A is matrix of coefficients, b is vector of constant terms.

*answer is x vector, given in rational numbers (fractions of pairs of very long integers).


The matrix A is dense (general case), but it can have up to 60 % of zero coefficients.
What is the best way (fastest algorithm for x86/x86_64) to solve such system?
Thanks!
PS typical answer of such systems have integers in fraction up to 50-80 digits long, so, please don't suggest anything based only on float/doubles. They have no needed precision.

The Dixon's algorithm is. It does a inversion of the matrix in modular arithmetic, based on some prime modulus P (this step is easy and exact). Then it solves the trivial system for each x to get a p-adic number representation of the solution. It can be converted to a rational number. Method was described in "Dixon J. D. Exact solution of linear equations using P-adic expansions // Numer. Math., 40, 1982, P. 137-141.", but this article is offline.
There is a article about Dixon's algorithm and its modifications online: http://www2.isye.gatech.edu/~dsteffy/papers/OSLifting.pdf
Author also have all described algorithms implemented and published at http://www2.isye.gatech.edu/~dsteffy/rational/
Another interesting approach is http://en.wikipedia.org/wiki/Montante's_method>Montante's method, which is a gauss variant for integer coefficient matrices. This variant don't create rational numbers in the matrix while converting it to triangular. Take a look at the last picture in link http://en.wikipedia.org/wiki/Montante's_method
