ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 08 Jun 2018 14:20:20 -0500Computing Roots of Large Polynomialshttp://ask.sagemath.org/question/42534/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][0].real(),sols[n][0].imag()]]
#solsPlot+=[[sols[n].real(),sols[n].imag()]]
scatter_plot(solsPlot)
Thanks.Wed, 06 Jun 2018 12:32:04 -0500http://ask.sagemath.org/question/42534/computing-roots-of-large-polynomials/Answer by tmonteil for <p>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:</p>
<pre><code>#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)
</code></pre>
<p>Thanks.</p>
http://ask.sagemath.org/question/42534/computing-roots-of-large-polynomials/?answer=42540#post-id-42540``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)Thu, 07 Jun 2018 01:04:50 -0500http://ask.sagemath.org/question/42534/computing-roots-of-large-polynomials/?answer=42540#post-id-42540Comment by tmonteil for <p><code>ComplexField()</code> (in short <code>CC</code>) is the field of floating-point numbers that are <em>emulated</em> by MPFR (with 53 bits of precision by default). If instead, you use the <code>ComplexDoubleField()</code> (in short <code>CDF</code>), that is the field of floating-point numbers that the processor can directly work with (with 53bits of precisions as well). Just replace <code>ComplexField()</code> with <code>CDF</code> in you code and you will see how faster it is.</p>
<p>That said, note that apparently you lose some roots on the way.</p>
<p>Note that exact computation does not give the same picture: if you use the rational field <code>QQ</code> instead of <code>ComplexField()</code> and look for the roots in the algebraic field <code>QQbar</code>, you get a different picture:</p>
<pre><code>sage: sols=s.roots(QQbar, multiplicities=False)
sage: points((i.real(),i.imag()) for i in sols)
</code></pre>
http://ask.sagemath.org/question/42534/computing-roots-of-large-polynomials/?comment=42554#post-id-42554You 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.Fri, 08 Jun 2018 13:55:11 -0500http://ask.sagemath.org/question/42534/computing-roots-of-large-polynomials/?comment=42554#post-id-42554Comment by Quinten87 for <p><code>ComplexField()</code> (in short <code>CC</code>) is the field of floating-point numbers that are <em>emulated</em> by MPFR (with 53 bits of precision by default). If instead, you use the <code>ComplexDoubleField()</code> (in short <code>CDF</code>), that is the field of floating-point numbers that the processor can directly work with (with 53bits of precisions as well). Just replace <code>ComplexField()</code> with <code>CDF</code> in you code and you will see how faster it is.</p>
<p>That said, note that apparently you lose some roots on the way.</p>
<p>Note that exact computation does not give the same picture: if you use the rational field <code>QQ</code> instead of <code>ComplexField()</code> and look for the roots in the algebraic field <code>QQbar</code>, you get a different picture:</p>
<pre><code>sage: sols=s.roots(QQbar, multiplicities=False)
sage: points((i.real(),i.imag()) for i in sols)
</code></pre>
http://ask.sagemath.org/question/42534/computing-roots-of-large-polynomials/?comment=42555#post-id-42555Thanks 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.Fri, 08 Jun 2018 14:20:20 -0500http://ask.sagemath.org/question/42534/computing-roots-of-large-polynomials/?comment=42555#post-id-42555Comment by Quinten87 for <p><code>ComplexField()</code> (in short <code>CC</code>) is the field of floating-point numbers that are <em>emulated</em> by MPFR (with 53 bits of precision by default). If instead, you use the <code>ComplexDoubleField()</code> (in short <code>CDF</code>), that is the field of floating-point numbers that the processor can directly work with (with 53bits of precisions as well). Just replace <code>ComplexField()</code> with <code>CDF</code> in you code and you will see how faster it is.</p>
<p>That said, note that apparently you lose some roots on the way.</p>
<p>Note that exact computation does not give the same picture: if you use the rational field <code>QQ</code> instead of <code>ComplexField()</code> and look for the roots in the algebraic field <code>QQbar</code>, you get a different picture:</p>
<pre><code>sage: sols=s.roots(QQbar, multiplicities=False)
sage: points((i.real(),i.imag()) for i in sols)
</code></pre>
http://ask.sagemath.org/question/42534/computing-roots-of-large-polynomials/?comment=42550#post-id-42550Thanks 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'.Fri, 08 Jun 2018 11:18:42 -0500http://ask.sagemath.org/question/42534/computing-roots-of-large-polynomials/?comment=42550#post-id-42550