## Re: [Maxima-discuss] allroots precision

 Re: [Maxima-discuss] allroots precision From: Raymond Toy - 2014-07-07 19:55:16 ```>>>>> "Stavros" == Stavros Macrakis <(Σταῦρος Μακράκης)" > writes: Stavros> ? allroots and ? bfallroots (unlike ? realroots) say Stavros> nothing about the precision of the result, or how to Stavros> control it (except the unhelpful "allroots may give Stavros> inaccurate results in case of multiple roots"). It would Stavros> be helpful if someone knowledgeable about the algorithms Stavros> could add some information about precision to the docs. allroots (and bfallroots) use Jenkins-Traub to compute the roots. AFAIK, there are no guarantees on accuracy. I do know accuracy degrades for multiple roots (or near multiples). And since deflation is used, the accuracy of the later roots is worse than the earlier roots. Having said that, I think the algorithm does produce a single root, r, of the polynomial, P, such that |P(r)| < eps where eps is approximately roundoff in computing the polynomial. Ray ```

 [Maxima-discuss] allroots precision From: Stavros Macrakis (Σταῦρος Μακράκης) - 2014-07-07 18:23:24 Attachments: Message as HTML ```? allroots and ? bfallroots (unlike ? realroots) say nothing about the precision of the result, or how to control it (except the unhelpful "allroots may give inaccurate results in case of multiple roots"). It would be helpful if someone knowledgeable about the algorithms could add some information about precision to the docs. -s ```
 Re: [Maxima-discuss] allroots precision From: Raymond Toy - 2014-07-07 19:55:16 ```>>>>> "Stavros" == Stavros Macrakis <(Σταῦρος Μακράκης)" > writes: Stavros> ? allroots and ? bfallroots (unlike ? realroots) say Stavros> nothing about the precision of the result, or how to Stavros> control it (except the unhelpful "allroots may give Stavros> inaccurate results in case of multiple roots"). It would Stavros> be helpful if someone knowledgeable about the algorithms Stavros> could add some information about precision to the docs. allroots (and bfallroots) use Jenkins-Traub to compute the roots. AFAIK, there are no guarantees on accuracy. I do know accuracy degrades for multiple roots (or near multiples). And since deflation is used, the accuracy of the later roots is worse than the earlier roots. Having said that, I think the algorithm does produce a single root, r, of the polynomial, P, such that |P(r)| < eps where eps is approximately roundoff in computing the polynomial. Ray ```
 Re: [Maxima-discuss] allroots precision From: Richard Fateman - 2014-07-07 22:04:29 ```On 7/7/2014 12:54 PM, Raymond Toy wrote: >>>>>> "Stavros" == Stavros Macrakis <(Σταῦρος Μακράκης)" > writes: > Stavros> ? allroots and ? bfallroots (unlike ? realroots) say > Stavros> nothing about the precision of the result, or how to > Stavros> control it (except the unhelpful "allroots may give > Stavros> inaccurate results in case of multiple roots"). It would > Stavros> be helpful if someone knowledgeable about the algorithms > Stavros> could add some information about precision to the docs. > > allroots (and bfallroots) use Jenkins-Traub to compute the > roots. AFAIK, there are no guarantees on accuracy. I do know accuracy > degrades for multiple roots (or near multiples). And since deflation > is used, the accuracy of the later roots is worse than the earlier > roots. This is a current research topic. (Not Jenkins-Traub, but rootfinding methods). Given that you cannot necessarily evaluate a polynomial accurately, it can be difficult to find its roots accurately. There are methods that find all roots at the same time, perhaps more accurately and more slowly. > > Having said that, I think the algorithm does produce a single root, r, > of the polynomial, P, such that |P(r)| < eps where eps is > approximately roundoff in computing the polynomial. > > Ray > > > > ------------------------------------------------------------------------------ > Open source business process management suite built on Java and Eclipse > Turn processes into business applications with Bonita BPM Community Edition > Quickly connect people, data, and systems into organized workflows > Winner of BOSSIE, CODIE, OW2 and Gartner awards > http://p.sf.net/sfu/Bonitasoft > _______________________________________________ > Maxima-discuss mailing list > Maxima-discuss@... > https://lists.sourceforge.net/lists/listinfo/maxima-discuss ```
 Re: [Maxima-discuss] allroots precision From: Stavros Macrakis (Σταῦρος Μακράκης) - 2014-07-07 22:56:14 Attachments: Message as HTML ```Understood that this is not a solved problem. However, it would be useful to give users who aren't familiar with Jenkins-Traub some guidance. I was also surprised that sols:allroots(eq:x^243+23*x-24) gives a warning: allroots: unexpected error; treat results with caution. allroots: only 65 out of 243 roots found. and the first element of the result list is a reduced polynomial. This behavior isn't warned against in the doc at all. I was somewhat less surprised that some values for subst(sol,eq) were pretty big -- that's the nature of the beast.... -s On Mon, Jul 7, 2014 at 6:04 PM, Richard Fateman wrote: > On 7/7/2014 12:54 PM, Raymond Toy wrote: > >>>>>> "Stavros" == Stavros Macrakis <(Σταῦρος Μακράκης)" < > macrakis@...>> writes: > > Stavros> ? allroots and ? bfallroots (unlike ? realroots) say > > Stavros> nothing about the precision of the result, or how to > > Stavros> control it (except the unhelpful "allroots may give > > Stavros> inaccurate results in case of multiple roots"). It would > > Stavros> be helpful if someone knowledgeable about the algorithms > > Stavros> could add some information about precision to the docs. > > > > allroots (and bfallroots) use Jenkins-Traub to compute the > > roots. AFAIK, there are no guarantees on accuracy. I do know accuracy > > degrades for multiple roots (or near multiples). And since deflation > > is used, the accuracy of the later roots is worse than the earlier > > roots. > This is a current research topic. (Not Jenkins-Traub, but rootfinding > methods). > Given that you cannot necessarily evaluate a polynomial accurately, it > can be > difficult to find its roots accurately. There are methods that find > all roots at the > same time, perhaps more accurately and more slowly. > > > > > Having said that, I think the algorithm does produce a single root, r, > > of the polynomial, P, such that |P(r)| < eps where eps is > > approximately roundoff in computing the polynomial. > > > > Ray > > > > > > > > > ------------------------------------------------------------------------------ > > Open source business process management suite built on Java and Eclipse > > Turn processes into business applications with Bonita BPM Community > Edition > > Quickly connect people, data, and systems into organized workflows > > Winner of BOSSIE, CODIE, OW2 and Gartner awards > > http://p.sf.net/sfu/Bonitasoft > > _______________________________________________ > > Maxima-discuss mailing list > > Maxima-discuss@... > > https://lists.sourceforge.net/lists/listinfo/maxima-discuss > > > > ------------------------------------------------------------------------------ > Open source business process management suite built on Java and Eclipse > Turn processes into business applications with Bonita BPM Community Edition > Quickly connect people, data, and systems into organized workflows > Winner of BOSSIE, CODIE, OW2 and Gartner awards > http://p.sf.net/sfu/Bonitasoft > _______________________________________________ > Maxima-discuss mailing list > Maxima-discuss@... > https://lists.sourceforge.net/lists/listinfo/maxima-discuss > ```
 Re: [Maxima-discuss] allroots precision From: Henry Baker - 2014-07-07 23:10:48 ```There are elegant (but not fast) exact polynomial root-location methods. The first step is to eliminate exact repeated roots using gcd(p(x),p'(x)). Then utilize exact methods to determine the exact number of roots within a rectangle in the complex plane with complex rational boundaris (i.e., in Q(i)). Once you have isolated a root within a rational box, you can either do a binary search and/or Newton methods to find it to much higher precision. Once you get close enough, Newton will quickly converge, but you need to get pretty close, and that might take an agonizingly long time if there are a lot of nearby roots. Also, Knuth describes an elegant method for extracting the continued fraction expansion of a polynomial root directly from the polynomial. Continued fractions don't converge as fast as Newton, but this is an interesting method, in any case. At 03:56 PM 7/7/2014, Î£ÏÎ±á¿¦ÏÎ¿Ï ÎÎ±ÎºÏÎ¬ÎºÎ·Ï wrote: >Understood that this is not a solved problem. However, it would be useful to give users who aren't familiar with Jenkins-Traub some guidance. > >I was also surprised that sols:allroots(eq:x^243+23*x-24) gives a warning: >allroots: unexpected error; treat results with caution. >allroots: only 65 out of 243 roots found. > >and the first element of the result list is a reduced polynomial. > >This behavior isn't warned against in the doc at all. > >I was somewhat less surprised that some values for subst(sol,eq) were pretty big -- that's the nature of the beast.... > > -s > >On Mon, Jul 7, 2014 at 6:04 PM, Richard Fateman wrote: >On 7/7/2014 12:54 PM, Raymond Toy wrote: >>>>>>> "Stavros" == Stavros Macrakis <(Î£ÏÎ±á¿¦ÏÎ¿Ï ÎÎ±ÎºÏÎ¬ÎºÎ·Ï)" > writes: >> Â Â Â Stavros> ? allroots and ? bfallroots (unlike ? realroots) say >> Â Â Â Stavros> nothing about the precision of the result, or how to >> Â Â Â Stavros> control it (except the unhelpful "allroots may give >> Â Â Â Stavros> inaccurate results in case of multiple roots"). It would >> Â Â Â Stavros> be helpful if someone knowledgeable about the algorithms >> Â Â Â Stavros> could add some information about precision to the docs. >> >> allroots (and bfallroots) use Jenkins-Traub to compute the >> roots. AFAIK, there are no guarantees on accuracy. I do know accuracy >> degrades for multiple roots (or near multiples). And since deflation >> is used, the accuracy of the later roots is worse than the earlier roots. > >This is a current research topic. (Not Jenkins-Traub, but rootfinding methods). >Given that you cannot necessarily evaluate a polynomial accurately, it can be >difficult Â to find its roots accurately. Â There are methods that find all roots at the >same time, perhaps more accurately and more slowly. > >> Having said that, I think the algorithm does produce a single root, r, >> of the polynomial, P, such that |P(r)| < eps where eps is >> approximately roundoff in computing the polynomial. >> >> Ray ```
 Re: [Maxima-discuss] allroots precision From: Richard Fateman - 2014-07-07 23:20:53 ```mcnamee has an enormous bibliography on this topic. Also see http://books.google.com/books/about/Numerical_Methods_for_Roots_of_Polynomia.html?id=j0rY3D9fx-0C ```
 Re: [Maxima-discuss] allroots precision From: Stavros Macrakis (Σταῦρος Μακράκης) - 2014-07-07 23:25:08 Attachments: Message as HTML ```Understood that there's a vast literature on all this. But what simple and correct statements can we make to help users understand what allroots does? ​​For example, could we say that for polynomials of degree < 20 and some characteristic of the coefficients, or of the roots, abs(calcroot-trueroot) < xxx? On Mon, Jul 7, 2014 at 7:20 PM, Richard Fateman wrote: > mcnamee has an enormous bibliography on this topic. Also see > > http://books.google.com/books/about/Numerical_Methods_for_ > Roots_of_Polynomia.html?id=j0rY3D9fx-0C > > ```
 Re: [Maxima-discuss] allroots precision From: Richard Fateman - 2014-07-07 23:40:59 Attachments: Message as HTML ```On 7/7/2014 4:25 PM, Stavros Macrakis (Σταῦρος Μακράκης) wrote: > Understood that there's a vast literature on all this. > > But what simple and correct statements can we make to help users > understand what allroots does? > > ​​For example, could we say that for polynomials of degree < 20 and > some characteristic of the coefficients, or of the roots, > abs(calcroot-trueroot) < xxx? I don't know for sure, but I am skeptical that anything both simple and so useful could be said. The classical example from Wilkinson http://en.wikipedia.org/wiki/Wilkinson's_polynomial is something like the polynomial product(x-n, n,0,25) whose roots are obvioiusly 0,1,2,...25. Allroots finds stuff like 16.23992085329114 -1.542591489044811*%i perturbing one of the coefficients by a trivial amount blows the accuracy to smithereens. Actually, Wilkinson's polynomial stopped at n=20, but allroots almost works at that point. See wikipedia for more info. RJF > > On Mon, Jul 7, 2014 at 7:20 PM, Richard Fateman > wrote: > > mcnamee has an enormous bibliography on this topic. Also see > > http://books.google.com/books/about/Numerical_Methods_for_Roots_of_Polynomia.html?id=j0rY3D9fx-0C > > ```
 Re: [Maxima-discuss] allroots precision From: Raymond Toy - 2014-07-08 16:21:43 ```>>>>> "Stavros" == Stavros Macrakis <(Σταῦρος Μακράκης)" > writes: Stavros> Understood that this is not a solved problem. However, it Stavros> would be useful to give users who aren't familiar with Stavros> Jenkins-Traub some guidance. The paper is available online at http://www.jstor.org/stable/2949376. It only says that the algorithm always converges (mathematically). A peek at the original Fortran code indicates that the algorithm converges when the polynomial value is smaller than a bound on the error in evaluating the polynomial. Stavros> I was also surprised that sols:allroots(eq:x^243+23*x-24) gives a warning: Stavros> allroots: Stavros> unexpected error; treat results with Stavros> caution. Stavros> allroots: Stavros> only 65 out of 243 roots found. Stavros> and the first element of the result list is a reduced polynomial. Stavros> This behavior isn't warned against in the doc at all. Oops. Yeah, that should be documented. Curiously, bfallroots finds all 243 roots even with fpprec = 16. Comparing with the roots with fpprec=100 shows that only the first 13 or so are correct. (I didn't check that roots were produced in the same order.) Ray ```