6
$\begingroup$

It is "well known" that a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$, $x\in \Bbb Z^n,b\in\Bbb Z^m$ for some $m,n \in \Bbb N$, can be solved in polynomial time, using Smith/Hermite Normal Form computation. By "solved" I mean either "decide, for a given $A,b$, whether a solution exists" or "decide whether a solution exists and output one". My question is:

Can we claim anything more specific than polynomial, such as cubic/quartic in $(m+n+\max{|A_{ij}}|)$? Or at least cubic/quartic if we assume that any arithmetic operation can be performed in unit time (ignoring possible blowup of the coefficients)?

The closest result I could find is in "Near optimal algorithms for computing Smith normal forms of integer matrices" by Storjohann where a nice complexity bound is presented for computing the Smith normal form, but it is not clear from the paper how to recover the unimodular transformation matrices (authors just write "In the future, we will present ... algorithm that compute (them)").

Another close result I found is this paper where a cubic algorithm is presented under the additional assumtion that we can use a unit-time oracle for computing greatest common divisor.

Another reference is this paper which deals with the case of non-singular square matrices. (Is there a simple reduction from a general $m\times n$ matrix to the non-singular square case?)

Another reference is this paper (thanks @Dima Pasechnik) which gives upper bounds on Hermite normal form computation, at least for the non-singular case: in the last section there is an outline how to generalize it for any matrices, but I again don't see how to recover the transformation matrix, as their algorithm does not use only elementary row/column operations.

$\endgroup$
10
  • $\begingroup$ Why Smith normal form? Hermite normal form suffices. $\endgroup$ Apr 20, 2016 at 8:07
  • $\begingroup$ Yes, I believe so, although it seems to me that it is still some work from the HNF to a solution. Can you give me a hint/reference? $\endgroup$ Apr 20, 2016 at 8:09
  • $\begingroup$ I think you should be more specific regarding what you mean by "solved". E.g. one may think of $b=0$ and $x$ being an infinite set (so no finite time, leave alone polynomial), or a basis of a $\mathbb{Z}$-lattice, or yet something else... $\endgroup$ Apr 20, 2016 at 9:01
  • 1
    $\begingroup$ OK - by the way, have a look at sciencedirect.com/science/article/pii/S0024379598100125 $\endgroup$ Apr 20, 2016 at 9:24
  • 1
    $\begingroup$ Is there any python or matlab codebase for solving such matrix system, especially for large dimensions say 1000? $\endgroup$ Nov 30, 2020 at 12:45

3 Answers 3

6
$\begingroup$

An improvement of Storjohann's result is due to Micciancio and Warinschi, A linear space algorithm for computing the Hermite normal form.

As to recovery of transformation matrices, in the classical algorithm one merely has to trace the elementary steps of the SNF/HNF computation; e.g. swapping rows/columns means that you have to multiply one of these matrices by the corresponding transposition; adding a row to another row means that you have to multiply one of them by the corresponding tranvection, etc. Note that these transformations are very sparse, i.e. these updates take much less time than general matrix multiplication.

Here it's less clear, and the computation is done modulo a number of primes, and this might give extra problems.

Storjohann and Labahn in Asymptotically fast computation of Hermite normal forms of integer matrices show how to compute unimodular $U$ so that $UA=H$, $H$ the HNF of $A$. There they require full column rank of $A$.

$\endgroup$
4
  • $\begingroup$ Thanks, it looks good. However, the main parts work only for square non-singular matrices. In the "Discussion" section, there are some hints on the general case,: "... one can first find a maximal set of linearly independent rows, and then find the HNF of the corresponding full-rank matrix." Is it clear that this can be done faster then the complexity bound given for the non-singular case? $\endgroup$ Apr 20, 2016 at 11:27
  • $\begingroup$ Further, I'm not sure if the authors only do "swapping rows/columns, adding rows to another row, etc". What about splitting a matrix $A$ to an upper-left part $B$, a right column $b$ and lower row $a^t$, recursively computing HNF of $B$ and then applying the AddRow / AddColumn sub-routines? I appreciate your effort but I still don't see how to elementary recover the transformation matrices. (What they do is not a simple Gaussian elimination.) $\endgroup$ Apr 20, 2016 at 11:39
  • $\begingroup$ how to compute the transformation (with a slightly worse complexity) is shown in "Asymptotically fast computation of Hermite normal forms of integer matrices" by Storjohann and Labahn: dx.doi.org/10.1145/236869.237083 $\endgroup$ Apr 20, 2016 at 12:08
  • $\begingroup$ I edited the answer to indicate what you say; indeed, it's not as clear. $\endgroup$ Apr 20, 2016 at 12:15
3
$\begingroup$

Ok, apparently, professor Storjohann sent me the reference I was looking for: Theorem 19 in A Fast Practical Deterministic Algorithm for Triangularizing Integer Matrices. (Thanks)

$\endgroup$
0
$\begingroup$

The best software I know for this purpose is

https://4ti2.github.io/

You will find specific theories in its references.

For really big systems, our ParAd

https://github.com/dazeorgacm/ParAd

makes solution in feasible time via clan composition

Dmitry Zaitsev, Stanimire Tomov, Jack Dongarra. Solving Linear Diophantine Systems on Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, 30(5), 2019, 1158-1169. DOI: 10.1109/TPDS.2018.2873354

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.