New Optimization Algorithms to Calculate Roots of Polynomials

[Namir]

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

[Luigi Vampa]

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.]

[Namir]

(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

[Claudio L.]

(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!

[Namir]

(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

[Albert Chan]

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 ?

[Namir]

(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

[Claudio L.]

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.

[Namir]

(08-09-2018 01:37 AM)Claudio L. Wrote:  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.

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

[ttw]

Discussion of condition numbers of various types of computations:

https://cs.uwaterloo.ca/conferences/hybr...avasis.pdf

[Thomas Klemm]

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

[Namir]

Thanks for the links!!

Namir

[Namir]

Anyone would are to try and write a program to calculate the condition number for polynomials???