8
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Just for comparison, you may like to test matsnf() function in the freeware PARI/GP: pari.math.u-bordeaux.fr $\endgroup$ – Max Alekseyev Jun 1 '15 at 7:27
  • 4
    $\begingroup$ 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! $\endgroup$ – Derek Holt Jun 1 '15 at 10:16
  • 1
    $\begingroup$ For a 120 x 120 matrix of random integers (as produced by RandomMatrix), Maple's SmithForm took 1.338 seconds. $\endgroup$ – Robert Israel Jun 1 '15 at 15:33
  • 2
    $\begingroup$ I am looking at matrices with polynomial entries. Sorry for the confusion. I am using the SNF functions provided by linear-algebra package. $\endgroup$ – Yibo Gao Jun 1 '15 at 17:34
  • 2
    $\begingroup$ For any large (and important) computation, you should consider checking multiple CAS's against each other. Eg Mathematica and Sage in addition to Maple. $\endgroup$ – Sam Nead Jul 31 '15 at 16:33
5
$\begingroup$

(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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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