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
--
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
