Almost two years ago, Linbox's implementation of Smith normal form was
taken out of Sage because it was too buggy. After some work, I managed
to reinstate it, hoping that the bugs might have been fixed. Here's a
partial status report:
1. I haven't tested it very broadly, but it seems to work on all of
the matrices that I feed it -- it agrees with Pari, anyway.
2. The Linbox implementation and the Pari implementation differ by a
transpose; that is, if you really want the two to agree on some matrix
m, you need to compare
m.elementary_divisors(algorithm='pari')
to
m.transpose().elementary_divisors(algorithm='linbox').
Actually, I just stuck the transpose into the elementary_divisors
function...
3. The timing is a bit odd. For a 105x455 sparse integer matrix m2,
this is what happened on my iMac with 2GB RAM:
sage: timeit('m2.dense_matrix().elementary_divisors
(algorithm="pari")')
5 loops, best of 3: 431 ms per loop
sage: timeit('m2.dense_matrix().elementary_divisors
(algorithm="linbox")')
5 loops, best of 3: 365 ms per loop
For a 719 x 1347 sparse integer matrix m6:
sage: timeit("m6.dense_matrix().elementary_divisors
(algorithm='pari')", number=1)
1 loops, best of 3: 23.9 s per loop
sage: timeit("m6.dense_matrix().elementary_divisors
(algorithm='linbox)", number=1)
1 loops, best of 3: 397 s per loop
One comment here: although the first timing says "23.9 s per loop", it
took about an hour for this to actually complete.
On sage.math, I got timings which are consistent with this (except
that here, the timings accurately reflect the wall time for the
command). Here, m7 is a 694 x1300 sparse integer matrix:
sage: timeit("m7.dense_matrix().elementary_divisors
(algorithm='pari')", number=1)
1 loops, best of 3: 14.7 s per loop
sage: timeit("m7.dense_matrix().elementary_divisors
(algorithm='linbox')", number=1)
1 loops, best of 3: 219 s per loop
So Linbox is faster for smaller matrices and Pari might be faster on
larger ones, depending on your computer. As far as I can tell, neither
has an implementation for sparse matrices which is accessible from
Sage. Does anyone know if Pari or Linbox have code explicitly for
Smith normal form for sparse matrices? It might be fun to see what
such code could do with these matrices...
Anyway, I'm not sure what conclusions to draw from this, except that I
should do my computations on sage.math :)
Finally, I was unable to do this successfully on the old ubuntu box in
my office: calling the linbox version of elementary_divisors on just a
2 x 3 matrix led to a RuntimeError. I have no idea how to fix this...
John
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
