Timeline for Solving a system of linear equations over the integers
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 6, 2018 at 0:35 | answer | added | Igor Rivin | timeline score: 8 | |
| Mar 5, 2018 at 23:56 | comment | added | Robin Houston |
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.
|
|
| Mar 5, 2018 at 23:50 | comment | added | Watson Ladd | Plus finding one solution. The challenge is really the efficiency. | |
| Mar 5, 2018 at 22:59 | comment | added | Robin Houston | 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}$.) | |
| Mar 5, 2018 at 22:05 | comment | added | Peter Heinig | 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). | |
| Mar 5, 2018 at 22:03 | comment | added | Gerhard Paseman | 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. | |
| Mar 5, 2018 at 21:53 | history | asked | Watson Ladd | CC BY-SA 3.0 |