FPGA Central

Hi,
I have been trying to solve the problem Roots of the polynomial 038
from mipt.ru (el judge). I have failed to do so. I tried to search on
the net but found about contour integrals for routh-hurwitz criterion.
So it is difficult to code.

Can you please tell me how to solve the problem for degree 20 ? and
how to approach the problem for degree 4.

Please do tell me the pseudo code and references.


Thanks,
Terry
[email protected]

In article <1125293735.090133.226[email protected] .com>,
<[email protected]> wrote:

> Hi,
> I have been trying to solve the problem Roots of the polynomial 038
> from mipt.ru (el judge). I have failed to do so. I tried to search on
> the net but found about contour integrals for routh-hurwitz criterion.
> So it is difficult to code.
>
> Can you please tell me how to solve the problem for degree 20 ? and
> how to approach the problem for degree 4.
>
> Please do tell me the pseudo code and references.

First of all, I don't have any idea what you're talking about. Give a
proper URL if you want an answer.

Second, you have posted THE SAME TEXT in two different posts, once to
sci.math and once to comp.dsp, sci.eng.control, and
sci.math.num-analysis. The one to three newsgroups is in approved
form, and doesn't increase bandwith. The one to sci.math DID increase
bandwidth.

I can guess what you mean from context, and it's not difficult to code.
All you have to do is estimate the derivative of f'(z)/f(z) on a
contour (all you need is an upper bound on the absolute value, so you
have a Lipschitz constant on the contour), then take a fine enough grid
on the parameterization of the contour so as to be able to recognize
the discretization of the integral as being close enough to an integral
multiple of 2 pi i. This yields the degree of the mapping, which is
the count of roots. Perfectly routine.


--Ron Bruck

[email protected] wrote:
> Hi,
> I have been trying to solve the problem Roots of the polynomial 038
> from mipt.ru (el judge). I have failed to do so. I tried to search on
> the net but found about contour integrals for routh-hurwitz criterion.
> So it is difficult to code.
>
> Can you please tell me how to solve the problem for degree 20 ? and
> how to approach the problem for degree 4.
>
> Please do tell me the pseudo code and references.
>
>
> Thanks,
> Terry
> [email protected]
>
The book "Numerical Recipes in C" has a polynomial root finder.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

"Tim Wescott" schrieb
>
> The book "Numerical Recipes in C" has a
> polynomial root finder.
>
I keep finding on the web references that are saying
that this book is less than optimal. What's the
opinion here? Any other good books about numerical
methods that can be recommended?

Regards
Martin

Martin Blume wrote:
> "Tim Wescott" schrieb
>
>>
>>The book "Numerical Recipes in C" has a
>>polynomial root finder.
>>
>
> I keep finding on the web references that are saying
> that this book is less than optimal. What's the
> opinion here? Any other good books about numerical
> methods that can be recommended?

If you mean by "less than optimal" that a clever programmer can write a
more efficient algorithm, that is often true. It is rarely true that the
routines don't perform as claimed. Avoiding NR because the code could
perhaps be improved is like choosing to walk because the bicycle you've
been offered is less than best.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

>>>>> "Jerry" == Jerry Avins <[email protected]> writes:

Jerry> Martin Blume wrote:
>> "Tim Wescott" schrieb
>>
>>> The book "Numerical Recipes in C" has a polynomial root finder.
>>>
>> I keep finding on the web references that are saying
>> that this book is less than optimal. What's the opinion here? Any
>> other good books about numerical methods that can be recommended?

Jerry> If you mean by "less than optimal" that a clever programmer can write
Jerry> a more efficient algorithm, that is often true. It is rarely true that
Jerry> the routines don't perform as claimed. Avoiding NR because the code
Jerry> could perhaps be improved is like choosing to walk because the bicycle
Jerry> you've been offered is less than best.

In this particular case, I think they usually mean the NR code is not
serious numerical code. It might work for simple cases, but it may be
very wrong for other cases. It may not even be all that accurate even
for the simple cases.

Ray

Raymond Toy wrote:
> In this particular case, I think they usually mean the NR code is not
> serious numerical code. It might work for simple cases, but it may be
> very wrong for other cases. It may not even be all that accurate even
> for the simple cases.
>

In a nutshell, it is often not optimized for correctness. ;-)

--
Jim Thomas Principal Applications Engineer Bittware, Inc
[email protected] http://www.bittware.com (603) 226-0404 x536
Nothing is ever so bad that it can't get worse. - Calvin

On Mon, 29 Aug 2005 15:20:14 -0400, Jerry Avins <[email protected]> wrote:
> Martin Blume wrote:
>> "Tim Wescott" schrieb
>>
>>>
>>>The book "Numerical Recipes in C" has a
>>>polynomial root finder.
>>>
>>
>> I keep finding on the web references that are saying
>> that this book is less than optimal. What's the
>> opinion here? Any other good books about numerical
>> methods that can be recommended?
>
> If you mean by "less than optimal" that a clever programmer can write a
> more efficient algorithm, that is often true. It is rarely true that the
> routines don't perform as claimed. Avoiding NR because the code could
> perhaps be improved is like choosing to walk because the bicycle you've
> been offered is less than best.
>

I've never found an instance where NR's code was "wrong" but the
examples are written more for teaching than for performance.

There WERE well known problems with earlier editions of the book, all of
which are noted in the notes.

HOWEVER, NR has EXCELLENT cross references that point to NUMEROUS
implementations, both free and commercial, of nearly all of the
algorithms.

Note the root finding is a tricky problem, as you're necessarily dealing
with very small numbers. Back when the 'c40 was all the rage, we ran
into quite a few problems when the guy implementing the root finding
algorithm "knew" he had it right, but forgot that the 'c40 didn't, by
default, didn't do things with enough accuracy for the kind of algorithm
he was using.

I sure learned a lot about numeric methods on That project.

Jerry Avins wrote:

> Martin Blume wrote:
>
>> "Tim Wescott" schrieb
>>
>>> The book "Numerical Recipes in C" has a polynomial root finder.
>>
>> I keep finding on the web references that are saying
>> that this book is less than optimal. What's the opinion here? Any
>> other good books about numerical methods that can be recommended?
>
> If you mean by "less than optimal" that a clever programmer can write a
> more efficient algorithm, that is often true. It is rarely true that the
> routines don't perform as claimed. Avoiding NR because the code could
> perhaps be improved is like choosing to walk because the bicycle you've
> been offered is less than best.

Some of the algorithms have a few serious faults too. And the odd typo
and quirky indexing from translation out of the original FORTRAN.

But you get what you deserve if you don't cross check that the answer
you get from a computer code is correct.

The references given in the book are still OK, and much of their code
only fails on difficult problems. If doesn't work for you then chase up
a more advanced text. It is still a pretty good general intro for all
its faults. There are much better standard libraries about.

Regards,
Martin Brown

Martin Brown wrote:
> Jerry Avins wrote:
>
>> Martin Blume wrote:
>>
>>> "Tim Wescott" schrieb
>>>
>>>> The book "Numerical Recipes in C" has a polynomial root finder.
>>>
>>>
>>> I keep finding on the web references that are saying
>>> that this book is less than optimal. What's the opinion here? Any
>>> other good books about numerical methods that can be recommended?
>>
>>
>> If you mean by "less than optimal" that a clever programmer can write
>> a more efficient algorithm, that is often true. It is rarely true that
>> the routines don't perform as claimed. Avoiding NR because the code
>> could perhaps be improved is like choosing to walk because the bicycle
>> you've been offered is less than best.
>
>
> Some of the algorithms have a few serious faults too. And the odd typo
> and quirky indexing from translation out of the original FORTRAN.
>
> But you get what you deserve if you don't cross check that the answer
> you get from a computer code is correct.
>
> The references given in the book are still OK, and much of their code
> only fails on difficult problems. If doesn't work for you then chase up
> a more advanced text. It is still a pretty good general intro for all
> its faults. There are much better standard libraries about.
>
> Regards,
> Martin Brown

The DSP group at Rice University have published Matlab code for solving
high order polynomials. I believe last year they published a paper in
the IEEE Signal Processing Magazine.

Solving polynomials is a difficult problem due to the numerical
sensitivity. Once you find some of the roots you have to deflate the
order of the polynomial. It's a similar problem to finding Eigenvalues.
So if you want the work you should probably be looking at the BLAS or
LINPACK libraries.

Cheers,
David

David Kirkland wrote:

> The DSP group at Rice University have published Matlab code for solving
> high order polynomials.

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


Bob
--

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

A. Einstein

temp[email protected] wrote:
>
> Can you please tell me how to solve the problem for degree 20 ? and
> how to approach the problem for degree 4.

Jenkins & Traub's "rpoly" code, celebrating its 30th anniversary, is
your best choice. You will find it at,

http://netlib.org/toms/493

---
bv
------------------------------------------------------
Applied Algorithms http://sdynamix.com

Bob Cain wrote:
>
>
> David Kirkland wrote:
>
>> The DSP group at Rice University have published Matlab code for
>> solving high order polynomials.
>
>
> http://www.dsp.rice.edu/software/fvhdp.shtml
>
>
> Bob

Thanks Bob

As I recall the website also has their publications.

Cheers,
David