# Computing Roots of Large Polynomials

Hey, I'm looking to compute the roots of very large polynomials (as in polynomials of degree 500+) and am looking for the most efficient method to do so. This my code so far (I tried a different method with the commented out code) and it works great for about anything with N<=200ish and then starts to take a really long time:

#var('x')
x=PolynomialRing(ComplexField(),'x').gen()
N=500
s=0
for m in range (N+1):
n=N+1-m
s+=(-1)^n*(n+1)*x^n/factorial(n)
#s+=[(-1)^n*(n+1)/factorial(n)]
#sols=(s==0).roots(x,ring=CC,multiplicities=False)
sols=s.roots()
solsPlot=[]
for n in range(len(sols)):
solsPlot+=[[sols[n].real(),sols[n].imag()]]
#solsPlot+=[[sols[n].real(),sols[n].imag()]]
scatter_plot(solsPlot)


Thanks.

edit retag close merge delete

Sort by » oldest newest most voted

ComplexField() (in short CC) is the field of floating-point numbers that are emulated by MPFR (with 53 bits of precision by default). If instead, you use the ComplexDoubleField() (in short CDF), that is the field of floating-point numbers that the processor can directly work with (with 53bits of precisions as well). Just replace ComplexField() with CDF in you code and you will see how faster it is.

That said, note that apparently you lose some roots on the way.

Note that exact computation does not give the same picture: if you use the rational field QQ instead of ComplexField() and look for the roots in the algebraic field QQbar, you get a different picture:

sage: sols=s.roots(QQbar, multiplicities=False)
sage: points((i.real(),i.imag()) for i in sols)

more

Thanks for the reply. I tried CDF and like you said it was a lot faster but a bunch of the roots also disappeared. The trouble is I'm not getting the picture I think I should. I think I should see one root converging to 1 and all the other ones going to infinity as for large N the series becomes increasingly close to z*exp(-z). I would be interested to see the picture you get using exact computation to see if it would be closer to my intuition but your code seems to give me the error 'Algebraic Field is not a valid variable'.

1

You might have missed something, my complete code is:

sage: x=PolynomialRing(ComplexField(),'x').gen()
sage: x = PolynomialRing(QQ,'x').gen()
sage: N = 200
sage: s = 0
sage: for m in range (N+1):
....:     n=N+1-m
....:     s+=(-1)^n*(n+1)*x^n/factorial(n)
sage: sols=s.roots(QQbar, multiplicities=False)
sage: points((i.real(),i.imag()) for i in sols)


The picture is bit different.

Thanks a lot! That's closer to what I was expecting when I went out to code the graph. I should have figured dividing by all those really huge numbers and then using numerical algorithms to pinpoint the roots would result in some massive errors.