[sage-support] Re: Some bugs and some wishes
On Feb 21, 12:36 am, emil wrote: > 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? And Martin A knows more than I do. ;-) (Thanks for your comments, Martin.) As Martin noted, the cutoff is not as arbitrary as I made it appear. (I was just too lazy to clean it up.) I would not call this a bug, it is just the current upper bound on optimized implementations. Martin has been doing a lot for fast linear algebra for specific cases, so we may be doing better in some cases (such as powers of 2). http://martinralbrecht.wordpress.com/2012/01/20/sage-4-8-is-out/ The fact that Mathematica does so much better in the original example posted might be some extra motivation to extend the current boundaries, but I can only speculate on how much work that would be. 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
Re: [sage-support] Re: Some bugs and some wishes
> 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? Actually, the cutoff changed: sage: type(Matrix(GF(previous_prime(2^23)),10,10)) sage: type(M) sage: %time M.right_kernel() CPU times: user 0.23 s, sys: 0.02 s, total: 0.25 s Wall time: 0.26 s Vector space of degree 1001 and dimension 1 over Finite Field of size 8388593 Basis matrix: 1 x 1001 dense matrix over Finite Field of size 8388593 sage: type(Matrix(GF(previous_prime(2^24)),10,10)) sage: M = MatrixSpace(GF(previous_prime(2^24)), 1000, 1001).random_element(); sage: %time M.right_kernel() ... wait a long long time This cutoff is not arbitrary btw. but such that the product of two elements fits into a double (53 bits). Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://martinralbrecht.wordpress.com/ _jab: martinralbre...@jabber.ccc.de -- 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
[sage-support] Re: Some bugs and some wishes
On 21 Feb., 06:18, Rob Beezer wrote:
> On Feb 16, 1:43 am, Manuel Kauers 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. =
> 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
[sage-support] Re: Some bugs and some wishes
On Feb 16, 1:43 am, Manuel Kauers 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. =
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
[sage-support] Re: Some bugs and some wishes
On 16 Feb., 10:43, Manuel Kauers wrote:
> Hi there,
>
> here are some bugs which may or may not be already known. If they are
> new, could you please file them wherever such bugs need to be filed? Or
> if they are not bugs but wrong usage, could you explain to me what I
> should type instead?
>
> I am still working with version 4.7.1, so some remarks might be obsolete
> already. (Sorry about that.)
>
> 1. When I have rational functions over a field [or over an integral
> domain], I expect that the denominator is made monic [or the content of
> numerator and denominator coprime]. This is not always happening. For
> example:
>
> sage: R. = QQ[]
> sage: (2*x+4)/(4*x-8)
> (2*x + 4)/(4*x - 8) # bad
> sage: R. = ZZ[]
> sage: (2*x+4)/(4*x-8)
> (x + 2)/(2*x - 4) # good
>
> Although mathematically correct, I consider this as a bug, because not
> bringing rational functions to normal form can easily lead to ridiculous
> expression swell. For example:
>
> sage: R1. = QQ[]
> sage: R2. = R1.fraction_field()[]
> sage: K = R2.fraction_field()
>
> sage: def canonic(rat):
> num, den = rat.numerator(), rat.denominator()
> clear = lcm(num.denominator(), den.denominator())
> num, den = num*clear, den*clear
> clear = map(lambda p: p.numerator().coeffs(), \
> num.coeffs() + den.coeffs())
> clear = lcm([a.denominator() for b in clear for a in b])
> num, den = num*clear, den*clear
> x = rat.parent().gen()
> t = rat.parent().base_ring().gen()
> return rat.parent()(ZZ[t,x](num)/ZZ[t,x](den))
>
> sage: d = K.random_element().derivative(y).derivative(x);
> sage: len(str(d))
> 919274
> sage: len(str(canonic(d)))
> 8371
>
> 2. A coercion problem?
>
> sage: K = QQ[x].fraction_field()
> sage: R. = K[]
> sage: S = QuotientRing(R, R.ideal(y^2-(x^2+1)))
> sage: ybar = S.gen()
> sage: S(y) # works
> ybar
> sage: 1/ybar # works
> (-1/(-x^2 - 1))*ybar
> sage: S(1/y) # doesn't work
> *** output flushed ***
> TypeError: denominator must be a unit
>
> 3. Another coercion problem?
>
> sage: R0 = QQ['t'].fraction_field(); t = R0.gen()
> sage: R1 = R0['x'].fraction_field(); x = R1.gen()
> sage: R2 = R1['y']; y = R2.gen()
> sage: R = QuotientRing(R2, R2.ideal(y^2-(x+t)))
> sage: ybar = R.gen()
> sage: ybar^2 # works
> x + t
> sage: ybar + x # works
> ybar + x
> sage: ybar * x # doesn't work
> *** output flushed ***
> NotImplementedError:
> sage: ybar*R(x) # works
> x*ybar
>
> 4. A bug in LCM:
>
> sage: u = QQ['u'].gen(); v = QQ[u].fraction_field()['v'].gen()
> sage: pol = ((u^2 - u - 1)/(-1/5*u^2 - u - 1))*v^2 + ((4/9*u^2 -
> 1/2)/(1/2*u - 2))*v + (2*u^2 - 1/2*u - 1/3)/(-2*u^2 - 5*u - 1/2)
> sage: lcm(pol, 1)
> *** output flushed ***
> TypeError: denominator must be a unit
>
> 5. The universe of a factorization cannot be changed if the
> factorization happens to be empty.
>
> sage: factor(2).base_change(ZZ['t','x']).universe()
> Multivariate Polynomial Ring in t, x over Integer Ring # correct
> sage: factor(1).base_change(ZZ['t','x']).universe()
> Integer Ring # incorrect
>
> 6. Resultants for elements of Quot(ZZ[t])[x,y] crash.
>
> sage: K = ZZ['t'].fraction_field(); t = K.gen()
> sage: R = K['x', 'y']; x,y = R.gens()
> sage: R.random_element().resultant(R.random_element(), y)
> *** Output flushed ***
> TypeError: denominator must be a unit
>
> 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}
>
> And here is a wish list of some things that I would find convenient to
> have, but didn't find.
>
> 1. a method .derivative for quotient ring elements, with which
> algebraic functions can be differentiated.
>
> 2. a method Factorization.square_free_part
>
> 3. a possibility to specify a variable in the method .minpoly for
> quotient ring elements. It is confusing that this method takes 'x' as
> variable for the minimal polynomial even if there is already an 'x' in
> the ground field.
>
> Thanks & best regards,
> Manuel
*bump*
I some of those are real "bugs" I could copy over these examples to
tickets on Sage Trac. Or do you want to create an account and file
those tickets yourself which would be preferable?.
--
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
