 New Optimization Algorithms to Calculate Roots of Polynomials - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: New Optimization Algorithms to Calculate Roots of Polynomials (/thread-11179.html) New Optimization Algorithms to Calculate Roots of Polynomials - Namir - 08-06-2018 01:35 PM Hi All, I posted here a PDF file than contains an article I wrote about two new algorithms that use optimization to calculate real and complex roots for real-coefficient polynomials. The algorithms are: 1) Newton-Vieta method that uses Newton's method to obtain teh real roots of the polynomial and then optimizes the Vieta Formulas to obtain the pair of conjugate complex roots from the deflated polynomial. 2) Quasi Lin-Bairstow method. A method that, like Lin-Bairstow, uses optimization to extract quadratic polynomials from a bigger polynomial using optimization. The extracted quadratic polynomials have either a pair of real roots or a pair of conjugate complex roots. Enjoy! Namir RE: New Optimization Algorithms to Calculate Roots of Polynomials - Luigi Vampa - 08-07-2018 08:53 AM I will carefully read it for good. Just as a suggestion, going for Octave, instead of Matlab, might help the readers to play with the provided code. Thanks for sharing this document, Namir. [EDIT: ... or maybe you can provide some guidelines about which commands could be the trouble makers. I was a Matlab campus user. Some years later I moved to Octave. Now it must be in a dusty spot in my brain.] RE: New Optimization Algorithms to Calculate Roots of Polynomials - Namir - 08-07-2018 09:56 PM (08-07-2018 08:53 AM)Luigi Vampa Wrote:  I will carefully read it for good. Just as a suggestion, going for Octave, instead of Matlab, might help the readers to play with the provided code. Thanks for sharing this document, Namir. [EDIT: ... or maybe you can provide some guidelines about which commands could be the trouble makers. I was a Matlab campus user. Some years later I moved to Octave. Now it must be in a dusty spot in my brain.] Luigi, I will make additional functions available for the HHC2018 and these functions have the optimizing part in the code. Namir RE: New Optimization Algorithms to Calculate Roots of Polynomials - Claudio L. - 08-08-2018 02:26 AM (08-06-2018 01:35 PM)Namir Wrote:  Hi All, I posted here a PDF file than contains an article I wrote about two new algorithms that use optimization to calculate real and complex roots for real-coefficient polynomials. The algorithms are: 1) Newton-Vieta method that uses Newton's method to obtain teh real roots of the polynomial and then optimizes the Vieta Formulas to obtain the pair of conjugate complex roots from the deflated polynomial. 2) Quasi Lin-Bairstow method. A method that, like Lin-Bairstow, uses optimization to extract quadratic polynomials from a bigger polynomial using optimization. The extracted quadratic polynomials have either a pair of real roots or a pair of conjugate complex roots. Enjoy! Namir Ahhhh... food for thought! Interesting as usual. I just finished implementing the multiple nonlinear equation solver for newRPL and went the optimization route as well. In my case I used the Nelder-Mead method, which I implemented from scratch from the description in Wikipedia. The method works really nice, but seems to be a bit picky with the initial guess. BTW, the basic root finder in newRPL was heavily inspired on your bisection experiments and improvements. Keep them coming! RE: New Optimization Algorithms to Calculate Roots of Polynomials - Namir - 08-08-2018 03:30 AM (08-08-2018 02:26 AM)Claudio L. Wrote:   (08-06-2018 01:35 PM)Namir Wrote:  Hi All, I posted here a PDF file than contains an article I wrote about two new algorithms that use optimization to calculate real and complex roots for real-coefficient polynomials. The algorithms are: 1) Newton-Vieta method that uses Newton's method to obtain teh real roots of the polynomial and then optimizes the Vieta Formulas to obtain the pair of conjugate complex roots from the deflated polynomial. 2) Quasi Lin-Bairstow method. A method that, like Lin-Bairstow, uses optimization to extract quadratic polynomials from a bigger polynomial using optimization. The extracted quadratic polynomials have either a pair of real roots or a pair of conjugate complex roots. Enjoy! Namir Ahhhh... food for thought! Interesting as usual. I just finished implementing the multiple nonlinear equation solver for newRPL and went the optimization route as well. In my case I used the Nelder-Mead method, which I implemented from scratch from the description in Wikipedia. The method works really nice, but seems to be a bit picky with the initial guess. BTW, the basic root finder in newRPL was heavily inspired on your bisection experiments and improvements. Keep them coming! MATLAN implements its fminsearch() optimization function using the Nelder-Mead method, so you are in good company. Namir RE: New Optimization Algorithms to Calculate Roots of Polynomials - Albert Chan - 08-08-2018 12:06 PM Hi, Namir: Nice article. Thanks. How good is the optimization ? Is benchmark data available ? About Matlab Particle Swarm Optimization function, how much speed does it contributed ? Is it proprietary code ? RE: New Optimization Algorithms to Calculate Roots of Polynomials - Namir - 08-08-2018 03:34 PM (08-08-2018 12:06 PM)Albert Chan Wrote:  Hi, Namir: Nice article. Thanks. How good is the optimization ? Is benchmark data available ? About Matlab Particle Swarm Optimization function, how much speed does it contributed ? Is it proprietary code ? Setting a benchmark for solving the roots of polynomial is a project all by itself. The issue here is correctness of solutions more so than speed. At for the particleswarm() function in Matlab 2018a I am sure Matlab has it coded in a robust way. None of my code I post is proprietary. Use it (and modified it) at your pleasure. Namir RE: New Optimization Algorithms to Calculate Roots of Polynomials - Claudio L. - 08-09-2018 01:37 AM I came across this page in Wikipedia: https://en.wikipedia.org/wiki/Test_functions_for_optimization It has a lot of functions to test optimization methods. Some are trickier than others. I thought it might be of interest to anyone trying optimization methods. RE: New Optimization Algorithms to Calculate Roots of Polynomials - Namir - 08-09-2018 03:05 AM (08-09-2018 01:37 AM)Claudio L. Wrote:  I came across this page in Wikipedia: https://en.wikipedia.org/wiki/Test_functions_for_optimization It has a lot of functions to test optimization methods. Some are trickier than others. I thought it might be of interest to anyone trying optimization methods. I used a good number of classical optimization algorithms with the Quasi Lin-Barstow algorithm to factor out quadratic equations from the targeted polynomial. Of course there is virtually an infinite number of polynomials to test. As the order of the polynomial increases so does the combination of polynomial coefficients. I came across several cases where where the optimization algorithms gave wrong answers!! The cases that I saw had the coefficients (as the power of each term) increase half way and then drop (something like x^10 + 2*x^9 -4*x^8+12*x^7+18*x^6-x^5+2*x^4-4*x^3-8*x^2+9*x+10 = 0). I am assuming there must be a polynomial property that determines how easy it is to solve for its roots. Such a property would be equivalent to the condition number of a matrix that determines how easy it is to solve a system of linear equations Namir RE: New Optimization Algorithms to Calculate Roots of Polynomials - ttw - 08-09-2018 03:57 AM Discussion of condition numbers of various types of computations: https://cs.uwaterloo.ca/conferences/hybrid2011/slides/SteveVavasis.pdf RE: New Optimization Algorithms to Calculate Roots of Polynomials - Thomas Klemm - 08-09-2018 11:30 AM From the linked slides "Condition Numbers of Numeric and Algebraic Problems": Quote:Condition number of a root of a univariate polynomial (…) Toh and Trefethen (Gautschi): condition number of root x∗ (relative perturbation to p, absolute perturbation to x∗) is . . . Exercise: FIGURE IT OUT! That's the spirit we like. No worries. It's revealed on the next slide. Cheers Thomas RE: New Optimization Algorithms to Calculate Roots of Polynomials - Namir - 08-09-2018 11:51 AM Thanks for the links!! Namir RE: New Optimization Algorithms to Calculate Roots of Polynomials - Namir - 08-10-2018 02:38 AM Anyone would are to try and write a program to calculate the condition number for polynomials???