# Computation time of Smith normal form in Maple

I am using Maple to compute the Smith normal form (SNF) of a $$120 \times 120$$ matrix and it seems that I will never get an answer back. I have checked my code for small cases and I believe that it is correct. When I try to compute the SNF for a $$24 \times 24$$ matrix, the real time and CPU time are about 0.1~0.2 seconds. I don't think it will take more than 3 hours for a $$100 \times 100$$ matrix. I have also tried it on several operating systems and the results are similar.

Anyway, what is the approximate time complexity of the computation time of SNF? Is there a limit for the matrix size in Maple to do SNF?

Thank you so much!

• Just for comparison, you may like to test matsnf() function in the freeware PARI/GP: pari.math.u-bordeaux.fr – Max Alekseyev Jun 1 '15 at 7:27
• When you say you checked your code, do you mean that you coded a complete SNF algorithm yourself? That would not be a good idea at all! – Derek Holt Jun 1 '15 at 10:16
• For a 120 x 120 matrix of random integers (as produced by RandomMatrix), Maple's SmithForm took 1.338 seconds. – Robert Israel Jun 1 '15 at 15:33
• I am looking at matrices with polynomial entries. Sorry for the confusion. I am using the SNF functions provided by linear-algebra package. – Yibo Gao Jun 1 '15 at 17:34
• For any large (and important) computation, you should consider checking multiple CAS's against each other. Eg Mathematica and Sage in addition to Maple. – Sam Nead Jul 31 '15 at 16:33

## 1 Answer

(Dense) Smith Normal Form is theoretically computable in $O(\|A\| \log \|A\| N^4\log N)$ time (Arne Storjohann, 1996). Storjohann was at Waterloo at the time, so I would not be surprised if that is the algorithm Maple uses. Sparse SNF is much faster.