Computing Roots of Large Polynomials

asked 2018-06-06 19:32:04 +0200

Quinten87
55 ●3 ●7

updated 2018-06-07 08:08:20 +0200

tmonteil
27323 ●31 ●202 ●514 http://wiki.sagemath.o...

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][0].real(),sols[n][0].imag()]]
    #solsPlot+=[[sols[n].real(),sols[n].imag()]]
scatter_plot(solsPlot)

Thanks.

edit retag flag offensive close merge delete

add a comment

answered 2018-06-07 08:04:50 +0200

tmonteil
27323 ●31 ●202 ●514 http://wiki.sagemath.o...

updated 2018-06-07 08:47:04 +0200

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)

edit flag offensive delete link

Comments

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'.

Quinten87 ( 2018-06-08 18:18:42 +0200 )edit

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.

tmonteil ( 2018-06-08 20:55:11 +0200 )edit

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.

Quinten87 ( 2018-06-08 21:20:20 +0200 )edit

add a comment

Computing Roots of Large Polynomials

1 Answer

Comments

Your Answer

Question Tools

Stats

Computing Roots of Large Polynomials edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Computing Roots of Large Polynomials