Is there any good complexity upper bound for checking satisfiability of a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$?
I found some estimate on computing the Smith Normal Form $N$ such that $SAT=N$ for invertible matrices $S$ and $T$, for example here: unfortunately, it is not very clear from the paper how the matrices $S$ and $T$ can be recovered, there is only one note at the end of Section 1 that they will do it "in the future".
I found a few other papers dealing with complexity of SNF, but either they only describe special cases (square, invertible..) or I couldn't see how to use them (without the unimodular matrices $S$ and $T^{-1}$).
I don't know whether I need to compute the Smith Normal Form at all.
The matrix I have in mind is a (co)boundary matrix between $k$- and $(k+1)$-simplices of a simplicial complex, if it helps.
Any help will be appreciated.
I would leave a comment but don't have the reputation: check out http://www.math.udel.edu/~lazebnik/papers/dioph2.pdf, which also looks to have several useful references (in particular http://www.math.tamu.edu/~rojas/kannanbachemhermitesmith79.pdf for algorithms to compute Smith normal form).