I have a linear system of equations $$Ax=b$$ where $A$ is an $N\times N$ matrix with integer values, and $b$ is a $N\times 1$ vector with integer values. Due to prior knowledge, I know that I am guaranteed that there exists exactly one rational solution $x$ such that $x=A^{-1}b$ (as well as that $A$ has full rank).
I am now searching for an algorithm in Matlab (or any other language which I can rewrite into Matlab) which provides the exact rational solution to this problem for a given $A$ and $b$, for example in the form
$\vec{x}=\frac{r}{s}\vec{t}$, where $r$ and $s$ are scalar integers and $t$ is an $N\times 1$ vector of integers, or in the form (Matlab notation) x=r./s
where r
and s
are $N\times 1$ integer vectors.
I have tried [r,s]=rat(A\b)
, which works for simple enough cases but quickly results in rounding problems (i.e. r./s
only approximates $x$, but I need the exact solution). Using symbolic calculations works; however, I have to compile the program to stand-alone, and the Matlab Compiler does not support the Symbolic Toolbox as far as I know and as far as I tried.
Some stats: $N$ should be allowed to be at least around $100$ or higher. The values in $A$ can become rather large, such that I am already now using int64
. I understand that at one point I will run into numeric problems, and it's sufficient for me to postpone these kinds of problems as long as possible (I am grateful for any solution, even if it only works for smaller $N$). However, I need the precise solution, and I prefer an error message over any approximation, no matter how good. Runtime of the algorithm is secondary, and it's OK if it needs an hour or so for $N=100$ (being more efficient is however a plus).