Some code for doing this was contributed to FLINT a while back. It will
be fast, when we eventually get it incorporated properly in FLINT. It's
been sitting in my inbox for some time and isn't even in the svn
repository for FLINT yet. I don't have benchmarks to give at present,
but I'll let you know when we do.
Bill.
On 23 Jan, 23:12, "William Stein" <[EMAIL PROTECTED]> wrote:
> 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/
-~----------~----~----~----~------~----~------~--~---
