On Tue, 23 Jan 2007 14:09:56 -0800, Kiran S. Kedlaya <[EMAIL PROTECTED]> wrote:
> Here's a benchmark I just tried, which annoys me.
>
> sage: def test1():
> ....: P.<x> = PolynomialRing(RationalField())
> ....: t = x^8 - 11*x^7 + x^5 - 1
> ....: for _ in xrange(1000):
> ....: t.complex_roots()
> ....:
> sage: time test1()
> CPU times: user 6.78 s, sys: 0.02 s, total: 6.80 s
> Wall time: 6.80
> sage: def test2():
> ....: t = pari("x^8 - 11*x^7 + x^5 - 1")
> ....: for _ in xrange(1000):
> ....: t.polroots()
> ....:
> sage: time test2()
> CPU times: user 6.15 s, sys: 0.00 s, total: 6.15 s
> Wall time: 6.15
> sage: %magma
> magma: procedure test3()
> magma: P<x> := PolynomialRing(RealField(53));
> magma: u := x^8 - 11*x^7 + x^5 - 1;
> magma: for i := 1 to 1000 do
> magma: t := Roots(u);
> magma: end for;
> magma: end procedure;
> magma: time test3();
> Time: 1.200
>
> The thing that bugs me is that Magma does not have some fancy
> proprietary algorithm for finding roots of a univariate polynomial; it
> uses PARI! So why are we so much slower?
Why do you think MAGMA uses PARI for this? (And this isn't so much
a problem with SAGE but with PARI.... Try the same computation
directly in PARI and it is just as slow.)
If you really want the answer to only 53-bits precision, by the way,
numpy can do it much much faster than MAGMA. For example,
sage: import numpy
sage: f = numpy.array([1,-11,0,1,0,0,0,0,-1]))
sage: numpy.roots(f)
sage: array([ 10.99172314+0.j , -0.72174425+0.j ,
-0.45332013+0.53432014j, -0.45332013-0.53432014j,
0.66182264+0.30451078j, 0.66182264-0.30451078j,
0.15650805+0.67766101j, 0.15650805-0.67766101j])
sage: time v=[numpy.roots(f) for _ in range(1000)]
CPU times: user 0.28 s, sys: 0.00 s, total: 0.28 s
Wall time: 0.28
That's already about 5 times faster than MAGMA. And I bet
that on larger degree numpy beats MAGMA by a lot more...
SAGE doesn't use numpy for root finding yet, partly because
numpy was added to SAGE only very recently, and I haven't
touched the root finding code in a while.
I've made this trac ticket #211.
William
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
