Solving a system of linear equations over the integers 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: To make sure I understand: you have an $m \times n$ matrix and vector in $\mathbb{Z}^n.$ Is the system a priori over- or under-determined? The former case is a little easier than the latter, but in any case, your problem is the so-called intermediate expression swell, and the easiest way to get around it is to solve it mod many primes and then chinese-remainder the results together. You don't actually need an a priori bound - you just find your solution mod $2, 3, \cdots, $ and keep chinese remaindering, until the result is actually a solution of the system (actually, the faster way is to work modulo as big primes as possible, so 32 bits primes, since the arithmetic is no slower than for small primes, and you will need fewer of them).
If your solution is actually unique over the real field, and the coefficients are not gigantic, you might consider just doing row-reduction by hand or, taking account of the fact that Sage is just a python front end, take the
 advice in this manual page: https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.solve.html
