Roots of a fractional polynomial with solve()

Hello everybody,

I'm looking for another method to solve this problem:

I have to find roots of a fractional polynomial:

syms mu real;
sum(lambda./(lambda-mu));
mu=double(solve(sum(lambda./(lambda-mu))/M-1/c==0,mu,'Real', true));

I used the function solve to find its roots. It's good but so slow! My polynom has a degree of 100 and i have to repeat this code in several random experiences.

Does anyone of you know a faster function which could do the same thing? I can't use fzeros().

Thanks for your help!

[Mischa Kim]

Just curious, why can't you use fzero ? Are you required to code it yourself?

[Alain]

Thanks for answering. No no. It's just because if I want to use fzeros I have to give a point near the root as a parameter to this function. But I have no idea of the value near the roots. That's why I can't use it...

[GOPAL SINGH]

plzz provide with some examples?

[Walter Roberson]

GOPAL SINGH as this question is 5 years old now, it would help if you were to explain more what you would like to have some examples of ?

Answer 1

[Walter Roberson]

I assume here that lambda is a vector of real values, and that M and c are scalars? If so then the expression can be rewritten without any fractional powers into a polynomial of degree length(lambda). The coefficients of the polynomial are of predictable form, with the N'th highest term involving all the combinations of elements in lambda taken (N-1) at a time, multiplied by (M/c - (N-1)).

I do not know if there are any special techniques for finding the roots of such a polynomial, but roots() can return all of the roots in numeric form.

[Alain]

Hello, I tried something similar that work. I used the function residue() which transforms my polynomial into the form P(mu)/Q(mu). It also gives all the coefficient of P(mu). Then I used roots(). It took only fews seconds so that's great! The roots are not exactly the same as with the function solve(). But it's still close.

[b,a]=residue(lambda,lambda,M/c);
mu=roots(b);

Thanks to all of you for your help. I hadn't realised immediately that all I had to do, was to change the fractional form and simplify it before doing the classical routine for roots!

[Alain]

Hello, I'm sorry to come again on this question, but I've just realised that my problem was actually unsolved!! :(

It's been weeks since the next steps of my code are a failure and I have understood that it was because the function roots() combined with the residue() function gave me roots with a lot of erros comparing to solve() function used alone...

I'm still tring to figure out a way to simplify or extract the numeratof of my frational polynomial without loosing precision. I used numden() which is really slow and now I don't know what else to try.

Does anyone have any ideas please?

[Bjorn Gustavsson]

I guess that the errors are because of the high order of the polynomial you send to roots. In that case you might be able to procced by rolling your own specialised vectorised Newton (for example) solver (since you have a polynomial) and use the results you get out of root as a start guess vector. If you're "lucky" all the roots will be found within a few iterations, if not you'd might have to repeat for the ones where convergence is not found.

Answer 2

[Mischa Kim]

Are you required to find all roots (<= 100!)?

At any rate, I'd recommend plotting the function to get a first impression on where some of the roots are located at and to be able to get starting values for the search(es). I am positive that you can use fzero to find some (if not all of the) roots, possibly in combination with a loop.

[Alain]

Yes I am... I thought about your method too. But the polynomial will change because I'm looking for the 100 roots in N random experiences. I can't plot them at each experience to assume where they are...

[Mischa Kim]

Now I understand. This bit of info just raised the level of complexity of the problem by an order of magnitude. Although MATLAB definitely is the tool to go with it is really the particular algorithm you are looking for to solve this class of problems. Let me see what I can dig up. Definitely one of the most interesting questions I have come across in this forum.

[Alain]

Thanks. I'm also searching on my side, because now I can't continue my code since all my next moves depend on those roots!

[Mischa Kim]

I might have some sort of a strategy, provided that the polynomials are somewhat well-behaved:

• Find all extrema of the polynomial using, e.g., the method/function presented here. Check out the third figure from the top. With this info you should be able to get good starting values for the searches.
• Solving for the roots of N experiments to me looks like a perfect problem for parallelization. Use the Parallel Computing Toolbox or, even better, the MDCS to speed up your algorithm.

What do you think?

[Alain]

Thanks for your advices Mischa.

• About the method of extrema. What do you have in mind exactly? I understand that if I have all the extrema, I could have an intervall of where each root is. So you suggest me to combine this information with fzeros?
• I don't know anything about this toolbox, since I'm quite new. But I'll have a look! But I don't think it's free,isn't it?

[Mischa Kim]

• Yep. Once you have all the extrema, you have pretty good starting values for all the roots. E.g., mid points between extrema. Then simply loop through all the starting values to get the roots with fzero.
• You might have the toolbox on your institution's license. If not you might qualify for a trial.

Let us know how this all panned out.

[Alain]

Hello Mischa. I tried the method of extrema. It failed. My polynomial is not exactly a polynomial: it's a fractional polynomial of the form P(mu)/Q(mu) (when you develop the form I gave you). Because of that form, many consecutive extremas are below 0. So it can't work...

[Mischa Kim]

I see. That's what I meant with well behaved. But I would not give up at this point.

1. Could you attach code, or maybe better, a plot of a typical polynomial?
2. Do the root locations change "much" when changing parameters?

[Alain]

No no I won't give up! :)

• You will have to zoom a lot to see what happens near zero.
• I don't feel like it's changing a lot. I attach also my roots values. Each line corresponds to one experience.
• Maybe I shoud more focus on a mathematical algorithm to find roots of fractional polynomial, rather than searching for Matlab functions firstly.

Thanks again for your help, I hope you are not wasting too much of your time for my problem! :)

[Bjorn Gustavsson]

Why give up when finding consecutive extremas lower (or larger) than 0, you still know that the root has to be between two extremas with varying sign, right? It might be unnecessarily time-consuming to find all when you can only utilize some, but it would still have some information you could use...