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