| Author |
Message |
John
Guest
|
 Posted:
Wed Nov 23, 2005 5:16 pm Post subject:
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... |
|
| Back to top |
|
 |
Rune Allnor
Guest
|
| Posted:
Wed Nov 23, 2005 5:16 pm Post subject:
Re: fastest way of calculating the roots of a polynomium?? |
|
|
John wrote:
| Quote: | 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 |
|
| Back to top |
|
|
John
Guest
|
| Posted:
Wed Nov 23, 2005 5:16 pm Post subject:
Re: fastest way of calculating the roots of a polynomium?? |
|
|
| Quote: | 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? |
|
| Back to top |
|
|
Emile
Guest
|
| Posted:
Wed Nov 23, 2005 5:16 pm Post subject:
Re: fastest way of calculating the roots of a polynomium?? |
|
|
John wrote:
| Quote: | 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 |
|
| Back to top |
|
|
dbell
Guest
|
| Posted:
Wed Nov 23, 2005 5:16 pm Post subject:
Re: fastest way of calculating the roots of a polynomium?? |
|
|
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 |
|
| Back to top |
|
|
Guest
|
| Posted:
Wed Nov 23, 2005 6:05 pm Post subject:
Re: fastest way of calculating the roots of a polynomials?? |
|
|
In article <43847dd4$0$67257$157c6196@dreader2.cybercity.dk>,
"John" <johnjohn@sucker.com> writes:
| Quote: | 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 |
|
| Back to top |
|
|
Karl Molnar
Guest
|
| Posted:
Wed Nov 23, 2005 8:43 pm Post subject:
Re: fastest way of calculating the roots of a polynomials?? |
|
|
In article <1132777446.921670.252430@o13g2000cwo.googlegroups.com>,
"Randy Yates" <yates@ieee.org> writes:
| Quote: | 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 |
|
| Back to top |
|
|
John
Guest
|
| Posted:
Wed Nov 23, 2005 11:31 pm Post subject:
Re: fastest way of calculating the roots of a polynomium?? |
|
|
Yes.
-----
< Do you *really* need them? Having spent a |
|
| Back to top |
|
|
Bob Cain
Guest
|
| Posted:
Thu Nov 24, 2005 1:16 am Post subject:
Re: fastest way of calculating the roots of a polynomium?? |
|
|
John wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Randy Yates
Guest
|
| Posted:
Thu Nov 24, 2005 1:16 am Post subject:
Re: fastest way of calculating the roots of a polynomials?? |
|
|
Karl,
I'm sorry I missed him. Was it a good meeting?
--Randy |
|
| Back to top |
|
|
John
Guest
|
| Posted:
Thu Nov 24, 2005 1:17 am Post subject:
Re: fastest way of calculating the roots of a polynomium?? |
|
|
| Thank you to you all :o) |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Sun Nov 27, 2005 1:16 am Post subject:
Re: fastest way of calculating the roots of a polynomium?? |
|
|
Emile wrote:
(snip)
| Quote: | 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).
|
For a simple root, that is fine. For a multiple root the derivative
goes to zero at the root, which is inconvenient for Newton's method.
-- glen |
|
| Back to top |
|
|
Randy Yates
Guest
|
| Posted:
Fri Dec 09, 2005 1:16 am Post subject:
Re: fastest way of calculating the roots of a polynomials?? |
|
|
I should've gone. Cool stuff, venerable men.
--Randy |
|
| Back to top |
|
|
Rick Lyons
Guest
|
| Posted:
Fri Dec 09, 2005 7:35 am Post subject:
Re: fastest way of calculating the roots of a polynomials?? |
|
|
On Wed, 23 Nov 2005 20:43:09 +0000 (UTC), molnar@rtp.ericsson.se (Karl
Molnar) wrote:
| Quote: | 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
|
Hi,
meeting Schafer and Kaiser must have been like
a baseball fan meeting Ted Williams & Mickey Mantle.
Neat.
[-Rick-] |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in