Polynomial root-finding

From: Alex Renelt (renelt_at_web.de)
Date: 03/03/05 

Date: Thu, 03 Mar 2005 20:54:47 +0100

Some time ago there was a discussion in this group about the "state of
the art" of certain polynomial root finders.

I'm writing a paper about polynomials and the process of zero finding
(plus implementations in python) for a german math course. I'm
considering the following methods as "sure-fire technics":

-companion matrix approach (QR-Algo. etc.)
To my mind stable, quiet fast, widely used but unsuited for higher
degrees (memory usage) and multiple zeros.

-jenkins-traub method (esp. rpoly)
For sure _one_ of the best methods but I don't like it much because
- for me - it seems to be quiet complicated and I hate deflation.

-laguerre
Also deflation... But my choice for fast initial approximations, e.g. for

-Durand-Kerner or Dochev or Weierstrass or what so ever called method
Wonderful simple. But stable? Some interesting modifications (see
Petkovic for example).
Is it used in any program or library you know?
There are some extensions to speed up the convergence for multiple
  zeros. But how to identify them during computation?

-Multroot (Matlab package, ACM Algo 835 I believe)
Needs a polynomial zero finder itself (matlab built in roots function).
Especially made for inexact coefficients and roots of high
multiplicities. I don't understand the method but it works - slowly but
quiet nice.

I'm asking everybody for suggestions about the "state of the art" of the
above mentioned methods (or additional ones).

Thanks a lot,

Alex

Relevant Pages

  • Re: Coefficients and Roots of a set of Polynomials
    ... This is just an idea to relate roots of polynomials and solutions of ... as roots symbolically for n even, ... 'Super' Organised Set for the Characteristic roots ... where the SumB result becomes zero for certain j index values ...
    (sci.math)
  • Re: algebraic integers - logarithmic expression
    ... |let Pbe the set of all irreducible monic polynomials with integer ... such that all roots are of modulus less than d. ... |zero and hence has a limit. ... By Eisenstein's irreducibility criterion ...
    (sci.math.research)
  • A little lesson for sqrt(144) year olds.
    ... difficulties with the concept of square roots: ... sqrt takes a positive (or zero) number ... Roots are things that make polynomials zero. ... things "square roots" or you will get utterly confused ...
    (sci.physics)
  • A little lesson for sqrt(144) year olds.
    ... difficulties with the concept of square roots: ... sqrt takes a positive (or zero) number ... Roots are things that make polynomials zero. ... things "square roots" or you will get utterly confused ...
    (sci.physics.relativity)
  • A little lesson for sqrt(144) year olds.
    ... difficulties with the concept of square roots: ... sqrt takes a positive (or zero) number ... Roots are things that make polynomials zero. ... things "square roots" or you will get utterly confused ...
    (sci.math)
Loading