fastest way of calculating the roots of a polynomium??

Hello

I am working on a speech enhancement algorithm. Part of my algorithm has to 
do with 10th order LPC-analysis that provides me with the real coefficients 
[a1,a2,.....,a10] for a 10th order polynomium 
A(z)=1+a1*(z^-1)+a2*(z^-2)+......+a10*(z^-10)

Is there a way to do fast calculation of all the roots of A(z) such that 
they are written on the complex form x+j*y ??

Thank you in advance...

Why do you want them?  If it is to check for stability, that is
normally done by checking the reflection coefficients which generated
for a lattice filter implementation.

Dirk

> Why do you want them?  If it is to check for stability, that is

It is not to check for stability....It is because I am more interested in 
finding the roots than the LPC-coefficients. If I have the roots I can 
quickly calculate the LPC-coefficients if I want to....so I am looking for a 
_fast_ way of determining the roots of a 10th order polynomial...I see that 
matlab solves it as an eigenvalue-problem....Is this the fastest way?

John wrote:
>>Why do you want them?  If it is to check for stability, that is
> 
> 
> It is not to check for stability....It is because I am more interested in 
> finding the roots than the LPC-coefficients. If I have the roots I can 
> quickly calculate the LPC-coefficients if I want to....so I am looking for a 
> _fast_ way of determining the roots of a 10th order polynomial...I see that 
> matlab solves it as an eigenvalue-problem....Is this the fastest way?
> 
> 
> 

I have had a course on computerarithmetics, there we used iterative 
methods to gradually come closer to the root(s) up to some arbitrary 
small error (by using the output of one iteration as input for the next, 
and stop when 2 successive iterations differ very little (other stopping 
conditions may be better but its usable), the fastest algorithm we've 
seen was the Newton-Raphson method (maybe not the fastest that exists). 
More numerical algorithms can be found here (maybe not the most complete 
explanation, but it should get u started):

http://mathworld.wolfram.com/topics/Root-Finding.html

grtz
Emile Vrijdags

John wrote:
> > Why do you want them?  If it is to check for stability, that is
>
> It is not to check for stability....It is because I am more interested in
> finding the roots than the LPC-coefficients. If I have the roots I can
> quickly calculate the LPC-coefficients if I want to....so I am looking for a
> _fast_ way of determining the roots of a 10th order polynomial...I see that
> matlab solves it as an eigenvalue-problem....Is this the fastest way?

I have solved roots in polynomials by using Laguerre's method. It works

reasonably well for 5th order polynomials, but requires a fair amount
of
fiddling to obtain a stable, robust method.

Before embarking on implementing such a routine, you should consider
why you want these roots. Do you *really* need them? Having spent a
bit of time with these things recently, I find it hard to justify the
effort
without a very compelling reason. For the record: The reason why I did
these things was that I wanted to represent IIR bandpass and bandstop
filters as a sequence of 2nd order sections. I am still debugging the
routines, three months after I started to implement them.

Rune

Yes.


-----
< Do you *really* need them? Having spent a

In article <43847dd4$0$67257$157c6196@dreader2.cybercity.dk>,

 "John" <johnjohn@sucker.com> writes:
>> Why do you want them?  If it is to check for stability, that is
>
>It is not to check for stability....It is because I am more interested in 
>finding the roots than the LPC-coefficients. If I have the roots I can 
>quickly calculate the LPC-coefficients if I want to....so I am looking for a 
>_fast_ way of determining the roots of a 10th order polynomial...I see that 
>matlab solves it as an eigenvalue-problem....Is this the fastest way?

Just went to a talk by Ron Shafer last night, and he talked about the problem
of finding roots of very high degree polynomials (up to order 1 million) using
a technique published in "Factoring Very High Degree Polynomials," IEEE Signal
Processing Magazine, November 2003.  You can get more info at
http://www-dsp.rice.edu/software/fvhdp.shtml

Regards,
Karl Molnar

Karl,

I'm sorry I missed him. Was it a good meeting?

--Randy

John wrote:
>> Why do you want them?  If it is to check for stability, that is
> 
> It is not to check for stability....It is because I am more interested in 
> finding the roots than the LPC-coefficients. If I have the roots I can 
> quickly calculate the LPC-coefficients if I want to....so I am looking for a 
> _fast_ way of determining the roots of a 10th order polynomial...I see that 
> matlab solves it as an eigenvalue-problem....Is this the fastest way?

No.  See:

   http://www.dsp.rice.edu/software/fvhdp.shtml


Bob
-- 

"Things should be described as simply as possible, but no simpler."

                                              A. Einstein

In article <1132777446.921670.252430@o13g2000cwo.googlegroups.com>,
 "Randy Yates" <yates@ieee.org> writes:
>Karl,
>
>I'm sorry I missed him. Was it a good meeting?
>
>--Randy
>

Randy,

It was interesting - he spoke about the history and application of the cepstrum.
As an added bonus, we also met Jim Kaiser.

Karl