Ask Your Question
3

Computing Roots of Large Polynomials

asked 2018-06-06 12:32:04 -0500

Quinten87 gravatar image

updated 2018-06-07 01:08:20 -0500

tmonteil gravatar image

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

1 answer

Sort by ยป oldest newest most voted
5

answered 2018-06-07 01:04:50 -0500

tmonteil gravatar image

updated 2018-06-07 01:47:04 -0500

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 more

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 gravatar imageQuinten87 ( 2018-06-08 11:18:42 -0500 )edit
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.

tmonteil gravatar imagetmonteil ( 2018-06-08 13:55:11 -0500 )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 gravatar imageQuinten87 ( 2018-06-08 14:20:20 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2018-06-06 12:32:04 -0500

Seen: 53 times

Last updated: Jun 07