Any expert for polynomial roots here?  Printable Version + HP Forums (https://archived.hpcalc.org/museumforum) + Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum1.html) + Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum2.html) + Thread: Any expert for polynomial roots here? (/thread204359.html) 
Any expert for polynomial roots here?  fhub  11082011 For my WP34s Polynomial RootSolver I've used the Bairstow method, but I also checked many other algorithms that I've found. One of these is the Laguerre method  here's a short WikiPedia article about it: It's stated there that this Laguerre method should be VERY powerful in 2 ways: it converges almost always (independent of the initial guesses), and it converges very quickly (usually 3rd order convergence). Now I made a 2nd version of my PolyRoots where I replaced the Bairstow method by this Laguerre method, and I'm absolutely disappointed: although it works correctly (i.e. finds the correct roots), it is damned slow  in average it needs about 35 times as many iterations as the Bairstow method (although it SHOULD be much better)! :(
Has anyone here experiences with polynomial rootsolving methods? Franz
Edited: 8 Nov 2011, 7:58 a.m. after one or more responses were posted
Re: Any expert for polynomial roots here?  Valentin Albillo  11082011 In case you haven't already, have a look at this, page 33 and beyond:
Best regards from V.
Re: Any expert for polynomial roots here?  Namir  11082011 Hello Franz, I use Bairstow's method when dealing with polynomials with real coefficients, because you should get all the rootsreal or complex. HP seems to favor the Laguerre method. As far as speed is concerned, I never thought that Bairstow is slow. Maybe you need to double check you source of equations and your implementation.
Namir
Re: Any expert for polynomial roots here?  fhub  11082011 Quote:Oh my god, a 11MB PDF document! ;)
Thanks, I'll have a look at it, Re: Any expert for polynomial roots here?  fhub  11082011 Ho Namir, Quote:Well, if I don't misunderstand what I've read then also Laguerre should give all (real+complex) roots!? The only problem could be that with real coefficients you always have pairs of complex conjugate solutions, and Laguerre doesn't seem to work very well if there are solutions with equal or similar absolute values (which is of course true for conjugates). Quote:I guess you're talking about PC implementations!? Well, for a PC program the speed (of Bairstow) is of course no big deal  even a few 1000 iterations don't need much time  but on slow hardware like 20/30b the speed is indeed a very important factor. And this is the reason why I was searching for eventually better (=faster) methods than Bairstow (although less than 5 sec for a 10thdegree polynomial is acceptable IMO).
I don't think that something in my implementation is wrong (or inefficient), both algorithms are so simple that it's almost impossible to do anything more complicated than necessary. Franz
Re: Any expert for polynomial roots here?  Alexander Oestert  11082011 Quote:Don't tell me you're still using a 14.4 modem... ;o Re: Any expert for polynomial roots here?  fhub  11082011 Quote:No, I didn't mean the download time but my old (and very weak) Win98 notebook that I'm using here: with about 70MB free RAM it even uses the Windows swapfile when I scroll through a 11MB PDF document! :(
But I just saw that I have already exactly the same HPJournal (found it when I made my HP71 emulator package), but my file is only 1MB compared to the version above with 11MB (nevertheless it has the same content).
Re: Any expert for polynomial roots here?  ArturBrazil  11092011 Great algorithms for implementing in HP15C !!!
Re: Any expert for polynomial roots here?  hugh steers  11092011 i can report that i use matrix methods for polynomial roots. essentially, i translate it into an eigenvalue problem. also i get complex results this way. results are usually stable and quite fast. im using a 14Mhz calculator for this. with this method, you dont have to extract pairs of roots at a time and reduce. so you dont have a forward error problem. however, Namir has done an indepth study of polynomial root problems. you might want to try his examples. my method also has problems with multiple roots, where i get imprecise results. so my approach is not foolproof.
Re: Any expert for polynomial roots here?  fhub  11102011 Quote:Yes, I know this method, but there are 2 problems (on the WP34s): First this would limit the polynomial solver to degree 10 (max. 10x10 matrices possible) and then the WP34s has no eigenvalues function, so _this_ would have to be written instead of a direct polyroots. And when I look at the method(s) for calculating eigenvalues (e.g. QR decompossition), I'm not sure if this would even fit into one flash region. Quote:Well, multiple roots are of course no principle problem because they can always be removed by reducing the polynomial P to P/gcd(P,P'), but that would also need many additional program steps for getting the gcd(P,P').
After having read through all the infos about the Laguerre method, now I know what makes this polynomial solver on the HP71 (which is based on the good old ZERPOL Fortran routine) so powerful: it's not the Laguerre method in the first, but the clever chosing and changing of initial values and/or iteration steps! So in fact this Laguerre method isn't that good at all, it works only well if you have VERY good initial values in every iteration step. This is probably the explanation for my bad experiences with my Laguerre program on the WP34s compared to the Bairstow method. Franz
Edited: 10 Nov 2011, 5:32 a.m.
Re: Any expert for polynomial roots here?  Valentin Albillo  11102011 Quote: Nope. Computing the gcd of two polynomials is pretty straightforward and fast, so it can be done if deemed useful.
Quote: Nope. You misunderstood Fig. 4 in page 35 in the HP Journal issue I referred you to. It doesn't say "roots", plural, but "root", singular, i.e., you need just one root of the modified polynomial, which the NewtonRaphson method gets you in a flash using the very good initial estimate provided. So it isn't that hard at all.
Quote: Nope. It is perfectly suitable, if correctly and efficiently implemented.
Quote: Nope on both counts. The Laguerre method is very good, that's why it was selected as the basis for the PROOT keyword in the HP71 Math ROM, and I think the explanation for your bad experiences lies somewhere else.
Best regards from V.
Re: Any expert for polynomial roots here?  fhub  11102011 Quote:Yes, straightforward and fast, but you need 3 routines for P', for gcd and polynomial division, and that's not done in a few bytes. Quote:Well, then why don't you make such a WP34s implementation? ;) Quote:And what should this reason be? It can't be any error in my code because else I won't get correct results. The reason is probably that I just use the origin (0/0) as initial guess and then random guesses in the interval [1,1] after every 25 unsuccessful iterations, but if the Laguerre method would really be as good as stated everywhere, than it would also work with _these_ guesses (and not require complicated calculations for 'good' initial values).
Franz
Re: Any expert for polynomial roots here?  fhub  11102011 Quote:I've read again this part, but I'm still not sure who of us is right!? This Cauchy lower bound RA is defined there as "minimum positive zero" of this modified polynomial, so IMO to be sure to really get the minimum you would have to calculate all roots. Ok, with the given (small) initial guess you'll rather get the minimum root first, but it's not absolutely sure. And furthermore I wonder why I would need this Cauchy bound as a 4th guess, when the 3 previous guesses are already so good!? So as I already stated: the 'power' of this PROOT routine is not the Laguerre method, but the big effort that is put into finding a good initial guess. But with such a good initial guess almost every other polynomial rootfinding algorithm would work just as well. Franz.
Edited: 10 Nov 2011, 10:27 a.m.
Re: Any expert for polynomial roots here?  Valentin Albillo  11102011 Quote: Nope. It can be done in a few bytes if correctly and efficiently implemented.
Quote: Got much better things to do with my time, and besides "been there, done that, bought the Tshirt". I already implemented a fullfledged, efficient polynomial solver for the HP41C back then in the golden days some 30 years ago so no need to repeat myself, see the relevant PPC issue if interested.
Quote: Nope, I haven't inspected your code but I'd hazard that the reason is your lack of relevant theoretical knowledge about the task you've set yourself up to.
Quote: Nope, they aren't complicated at all, it's your lack of understanding that makes them seem complicated to your eyes, thus resulting in you unfairly critizicing something which you simply fail to understand.
Quote: I'll give you a hint: you're wrong.
Quote: Nope, you don't need all roots at all, you only need a very specific one. It's just your lack of relevant theoretical understanding getting in the way, may I suggest you get and study any of the many good books on the subject, "Higher Algebra" by Kurosh is one of the best.
Quote: Nope, you're wrong in all counts but I won't push the matter further, I've already suggested that you learn the theory of what you're trying to accomplish lest you'll waste tons of effort to get a mediocre implementation at best.
Best regards from V.
Re: Any expert for polynomial roots here?  fhub  11102011 It seems "nope" is the only word in your quite limited vocabulary! And I'm really tired of discussing with such an arrogant and unfriendly guy. Unfortunately you're not the only one of this kind here in this forum, and so I'm now finally leaving this place full of allknowing 'gods'.
Bye, Re: Any expert for polynomial roots here?  Peter Murphy (Livermore)  11102011 I am shocked.
Re: Any expert for polynomial roots here?  Ángel Martin  11102011 Here´s Valentin´s program from PPC TN  slightly changed for the 41Z consumption (very obvious places and easy to undo)
1 LBL "ZPROOT" 87 E3 Re: Any expert for polynomial roots here?  Ángel Martin  11112011 and here are the roots found by the program for Valentin´s second example:
x^20+10 x^19+55 x^18+210 x^17+615 x^16+1452 x^15+2850 x^14+
1,473J7,264 execution time on V41: about 8 seconds (TURBO mode of course). It´s included in the 41Z module, so just load the image MOD file and turn it loose. Write or wrong? Easy enough to check ...
Edited: 11 Nov 2011, 2:13 a.m.
Re: Any expert for polynomial roots here?  Walter B  11112011 Quote:17 and counting [;) Re: Any expert for polynomial roots here?  Bart (UK)  11112011
Quote:Of which you are one as well. I probably am too at times :) Re: Any expert for polynomial roots here?  Gerson W. Barbosa  11112011 According to WolframAlpha there are the following coincident roots:
x = 1/2  sqrt(3)/2*i Cheers, Gerson.
