9
$\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!

Improve this question
$\endgroup$
8
  • 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
    Commented Jun 1, 2015 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
    Commented Jun 1, 2015 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
    Commented Jun 1, 2015 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
    Commented Jun 1, 2015 at 17:34
  • 3
    $\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
    Commented Jul 31, 2015 at 16:33

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$
3

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .