On 21 Feb., 06:18, Rob Beezer <goo...@beezer.cotse.net> wrote:
> On Feb 16, 1:43 am, Manuel Kauers <man...@kauers.de> wrote:
>
> > 7. Nullspace for matrices over finite fields is unreasonably slow
>
> > sage: M = MatrixSpace(GF(2^31-1), 1000, 1001).random_element();
> > sage: %time M.right_kernel();
> > CPU times: user 165.71 s, sys: 0.01 s, total: 165.73 s
> > Wall time: 166.20 s
>
> > Mathematica does this almost 20 times as fast:
>
> > In[5]:= mat = Table[RandomInteger[{0,2^31-1}], {n,0,1000},{k,0,1001}];
> > In[6]:= Timing[NullSpace[mat, Modulus -> 2^31-1];]
> > Out[6]= {8.98856, Null}
>
> It is the size of the prime here that matters. The kernel of a matrix
> is quite fast for "small" primes, but there is obviously room for
> improvement for larger primes. The cutoff is at
>
> sage.ext.multi_modular.MAX_MODULUS == 46341
>
> Timings of Mathematica 6.0 on sage.math:
>
> sage: mathematica_console()
> Mathematica 6.0 for Linux x86 (64-bit)
> Copyright 1988-2007 Wolfram Research, Inc.
>
> In[1]:= mat = Table[RandomInteger[{0,2^31-1}], {n,0,1000},{k,
> 0,1001}];
> In[2]:= Timing[NullSpace[mat, Modulus -> 2^31-1];]
> Out[2]= {9.54, Null}
>
> In[3]:= mat = Table[RandomInteger[{0,46049}], {n,0,1000},{k,0,1001}];
> In[4]:= Timing[NullSpace[mat, Modulus -> 46049];]
> Out[4]= {5.06, Null}
>
> Timings for Sage 4.8 on sage.math:
>
> sage: M = MatrixSpace(GF(2^31-1), 1000, 1001).random_element();
> sage: %time M.right_kernel();
> CPU times: user 209.69 s, sys: 0.11 s, total: 209.80 s
>
> sage: M = MatrixSpace(GF(46049), 1000, 1001).random_element();
> sage: %time M.right_kernel();
> CPU times: user 0.79 s, sys: 0.00 s, total: 0.79 s
>
> About 6 times faster. How does Mathematica do on finite fields with
> more structure?
>
> sage: sage: K.<a> =
> GF(101^2)
> sage:
> K
> Finite Field in a of size
> 101^2
> sage: sage: M = MatrixSpace(K, 1000, 1001).random_element();
> sage: sage: %time M.right_kernel();
> CPU times: user 89.87 s, sys: 0.06 s, total: 89.93 s
>
> Rob
Hi Rob, you understand more than I do - is this a bug (big step of
time needed for that type of calculation at an rather arbitrary
number)? Should I create a track ticket for that? Do you have also an
opinion on the various other points?
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
