I have a matrix with integral entries $A$ and integer vector $b$, and want to determine if there is exactly one vector $x$ such that $Ax=b$. $A$ is rectangular, and I know there always is a solution.

Now, Sage has a wonderful function to calculate this: solve_right. But when the input matrix and vector have dimensions around $1600$ this function eats up a lot of time and memory: 5 gigabytes and a lot of time before I finally killed it. Using the real field doesn't work either because Sage only solves linear equations with square matrices over the real field.

Are there any approaches to the above problem? Perhaps I can figure out some bounds on coefficients that would let me work over a large finite field.

A sharp bound for solutions of linear Diophantine equations, Proc. Amer. Math. Soc. 105 (1989), 844-846] to be the best result in this regard (though there might of course be more recent and better tools available). $\endgroup$`.elementary_divisors()`

function seems to be faster than`.solve_right()`

. But it’s probably still prohibitively slow at your dimensions. $\endgroup$