On Feb 4, 2:31 am, mabshoff <[email protected]> wrote:
> On Feb 3, 10:52 pm, John H Palmieri <[email protected]> wrote:
[snip]
> > 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.
>
> Well, it says "1 loops, best of 3: 23.9 s per loop", so I would used
> time not timeit to measure performance. Since it takes many seconds at
> least for those examples it is pointless anyway to run them in a loop.
> We might cache the pari result, but not the LinBox one, so that might
> explain the discrepancies.
The elementary_divisors function caches all of its results, but since
these are being run on essentially a new matrix each time (because of
the "dense_matrix" call), I don't think anything is getting cached
here. This seems to be confirmed by other experiments.
> > 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.
>
> I don't think that is possible, but you might be seeing some artifact.
> How do you create those matrices? Maybe they have a special structure?
They do have a special structure. They have at most 9 or 10 nonzero
entries in each column, and each nonzero entry is either 1 or -1. I
don't know why Pari would be faster than Linbox with these on
sage.math, and I don't know what the issue is with the timing on the
iMac, or why it was so different between the iMac and sage.math.
Maybe it's a memory issue.
Just now I tried the two algorithms on sage.math on random_matrix(ZZ,
50, 2^16) (I meant to use 'x=2^16', but this is probably more
interesting, timing-wise), and linbox took about half the time that
pari did. I also compared these on
m = random_matrix(ZZ, 1000, sparse=True, density=0.015, x=2)
Pari: Wall time: 546.47 s
Linbox: Wall time: 208.17 s
The numbers for Pari for my matrix m7 just don't make sense to me...
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
-~----------~----~----~----~------~----~------~--~---
