On Mon, Mar 31, 2008 at 4:27 PM, Mike Hansen <[EMAIL PROTECTED]> wrote:
>
> Hi Roman,
>
> It seems that for characteristic 0, Maxima is quite a bit faster than
> Singular, but there's some overhead in talking to Maxima over the
> pexpect interface. In any case, it is still _way_ slower than what we
> need. For example, Maxima takes around 10 seconds to do the bivariate
> gcd of degree 100 listed here (
> http://magma.maths.usyd.edu.au/users/allan/gcdcomp.html ). Magma on
> the other hand takes 0.06 seconds.
Even with the overhead Maxima is totally and completely unacceptable.
To take Joel Mohler's example of
t=-p10^170*X1^10*X2^10+p10^130*X1^10*X2^5+p10^130*X1^5*X2^10-p10^90*X1^5*X2^5+p10^80*X1^5*X2^5-p10^40*X1^5-p10^40*X2^5+1
I just tried this in Maxima, and it's been sitting there for about
*FIFTEEN MINUTES*:
sage: time
maxima.eval('factor(-p10^170*X1^10*X2^10+p10^130*X1^10*X2^5+p10^130*X1^5*X2^10-p10^90*X1^5*X2^5+p10^80*X1^5*X2^5-p10^40*X1^5-p10^40*X2^5+1)')
... fifteen minutes and still going ...
Magma, on the other hand is instant!
sage: R.<p10,g0,g1,g2,g3,g4,X1,X2>=ZZ[]
sage:
t=-p10^170*X1^10*X2^10+p10^130*X1^10*X2^5+p10^130*X1^5*X2^10-p10^90*X1^5*X2^5+p10^80*X1^5*X2^5-p10^40*X1^5-p10^40*X2^5+1
sage: s = magma(t)
sage: print magma.eval('time Factorization(%s)'%s.name())
[
<p10^8*X2 - 1, 1>,
<p10^8*X1 - 1, 1>,
<p10^18*X1*X2 - 1, 1>,
<p10^32*X2^4 + p10^24*X2^3 + p10^16*X2^2 + p10^8*X2 + 1, 1>,
<p10^32*X1^4 + p10^24*X1^3 + p10^16*X1^2 + p10^8*X1 + 1, 1>,
<p10^72*X1^4*X2^4 + p10^54*X1^3*X2^3 + p10^36*X1^2*X2^2 + p10^18*X1*X2 + 1, 1>
]
Time: 0.000
Since the goal of Sage is to be a viable alternative to Maple,Magma,Matlab,
and Mathematica, and Maxima just doesn't hack it speed wise, the only choice
is to implement something ourselves. E.g., the code Joel posted at
http://trac.sagemath.org/sage_trac/ticket/2179 does the above example in
about 0.10 seconds. That's a good start.
The important thing isn't what algorithm is implemented, but that the result
is fast(er than Magma).
-- William
> --Mike
>
>
>
> On Mon, Mar 31, 2008 at 3:39 PM, Roman Pearce <[EMAIL PROTECTED]> wrote:
> >
> > Please excuse a (possibly naive) suggestion, but why not use Maxima
> > for multivariate gcds and factorization ? I looked at the source code
> > and it appears to do Hensel lifting for both. That is the correct
> > algorithm that Sage appears to need. I'm not sure how to run it mod p
> > or over GF(p^q), but it must be possible.
> >
> > >
> >
>
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
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
-~----------~----~----~----~------~----~------~--~---
