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.