New Optimization Algorithms to Calculate Roots of Polynomials

08062018, 01:35 PM
(This post was last modified: 08062018 01:38 PM by Namir.)
Post: #1




New Optimization Algorithms to Calculate Roots of Polynomials
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 realcoefficient polynomials. The algorithms are: 1) NewtonVieta 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 LinBairstow method. A method that, like LinBairstow, 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 

08072018, 08:53 AM
(This post was last modified: 08072018 08:58 AM by Luigi Vampa.)
Post: #2




RE: New Optimization Algorithms to Calculate Roots of Polynomials
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.] Saludos Saluti Cordialement Cumprimentos MfG BR + + + + + Luigi Vampa + Free42 '<3' I + + 

08072018, 09:56 PM
Post: #3




RE: New Optimization Algorithms to Calculate Roots of Polynomials
(08072018 08:53 AM)Luigi Vampa Wrote: I will carefully read it for good. Luigi, I will make additional functions available for the HHC2018 and these functions have the optimizing part in the code. Namir 

08082018, 02:26 AM
Post: #4




RE: New Optimization Algorithms to Calculate Roots of Polynomials
(08062018 01:35 PM)Namir Wrote: Hi All, 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 NelderMead 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! 

08082018, 03:30 AM
Post: #5




RE: New Optimization Algorithms to Calculate Roots of Polynomials
(08082018 02:26 AM)Claudio L. Wrote:(08062018 01:35 PM)Namir Wrote: Hi All, MATLAN implements its fminsearch() optimization function using the NelderMead method, so you are in good company. Namir 

08082018, 12:06 PM
Post: #6




RE: New Optimization Algorithms to Calculate Roots of Polynomials
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 ? 

08082018, 03:34 PM
Post: #7




RE: New Optimization Algorithms to Calculate Roots of Polynomials
(08082018 12:06 PM)Albert Chan Wrote: Hi, Namir: 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 

08092018, 01:37 AM
Post: #8




RE: New Optimization Algorithms to Calculate Roots of Polynomials
I came across this page in Wikipedia:
https://en.wikipedia.org/wiki/Test_funct...timization 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. 

08092018, 03:05 AM
Post: #9




RE: New Optimization Algorithms to Calculate Roots of Polynomials
(08092018 01:37 AM)Claudio L. Wrote: I came across this page in Wikipedia: I used a good number of classical optimization algorithms with the Quasi LinBarstow 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^6x^5+2*x^44*x^38*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 

08092018, 03:57 AM
Post: #10




RE: New Optimization Algorithms to Calculate Roots of Polynomials
Discussion of condition numbers of various types of computations:
https://cs.uwaterloo.ca/conferences/hybr...avasis.pdf 

08092018, 11:30 AM
Post: #11




RE: New Optimization Algorithms to Calculate Roots of Polynomials
From the linked slides "Condition Numbers of Numeric and Algebraic Problems":
Quote:Condition number of a root of a univariate polynomial That's the spirit we like. No worries. It's revealed on the next slide. Cheers Thomas 

08092018, 11:51 AM
Post: #12




RE: New Optimization Algorithms to Calculate Roots of Polynomials
Thanks for the links!!
Namir 

08102018, 02:38 AM
Post: #13




RE: New Optimization Algorithms to Calculate Roots of Polynomials
Anyone would are to try and write a program to calculate the condition number for polynomials???


« Next Oldest  Next Newest »

User(s) browsing this thread: