5
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Usually one can compute the null space of A to determine if it has a nonzero vector. Since your A has integer entries, the null space will too. Is there a reason this will not help you? Gerhard "This Is A Singular Problem?" Paseman, 2018.03.05. $\endgroup$
    – Gerhard Paseman
    Commented Mar 5, 2018 at 22:03
  • 2
    $\begingroup$ Re "Perhaps I can figure out some bounds on coefficients that would let me work over a large finite field.": when I was working on similar problems I thought [I. Borosh, M. Flahive, D. Rubin, B. Treybig, 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$
    – Peter Heinig
    Commented Mar 5, 2018 at 22:05
  • $\begingroup$ Isn’t this equivalent to asking whether there is a non-zero vector $x$ such that $Ax=0$? (If $x_1$ and $x_2$ are solutions to $Ax=b$ then $x_1-x_2$ is a solution to $Ax=0$, and conversely if $Ax=b$ and $Ax'=0$ then $A(x+kx')=b$ for all $k\in\mathbb{Z}$.) $\endgroup$
    – Robin Houston
    Commented Mar 5, 2018 at 22:59
  • $\begingroup$ Plus finding one solution. The challenge is really the efficiency. $\endgroup$
    – Watson Ladd
    Commented Mar 5, 2018 at 23:50
  • $\begingroup$ Ah, I didn’t realise you need to find $x$ as well as determining if it’s unique. In that case the following is less relevant. But anyway: the .elementary_divisors() function seems to be faster than .solve_right(). But it’s probably still prohibitively slow at your dimensions. $\endgroup$
    – Robin Houston
    Commented Mar 5, 2018 at 23:56

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ A priori underdetermined,and I need to know if the solution is unique as well. Thanks for your answer: I'll try it and see if it works. $\endgroup$
    – Watson Ladd
    Commented Mar 6, 2018 at 2:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .