Re: Finding only some roots of a polynomial

[Ben Abbott]

On Oct 8, 2009, at 7:58 PM, Pablo wrote:

> Hi everyone!
>
> I need to find the roots of some quite big polynomials (order ~800).  
> The
> root function works fine (and surprisingly fast!), but I don't think
> it's the best tool forwhat I need. I'm only interested in those roots
> with high absolute value, so after "roots" works hard to find the 800
> complex values, I discard almost all of them.
>
> Do you have any suggestion for an algorithm to do that?
>
> I did find a book on the subject (McNamee - Numerical Methods for  
> Roots
> of Polynomials, Vol1 - 2007), and it suggest (I didn't read it
> thoroughly, yet) that the companion method finds the roots one by one,
> starting with the one with the largest magnitude. However, there are a
> multitude of similar methods in the book.
>
> Is Octave doing that?

Octave uses a different approach.

Octave constructs a matrix whose  characteristic polynomial is the  
same as the polynomial whose roots are desired. The eigen values of  
that matrix are then solved for (which are equal to the roots of the  
characteristic polynomial).

        http://en.wikipedia.org/wiki/Characteristic_polynomial

For info on how Octave calculates the eigen values, type "help eig" at  
Octave's prompt.

Ben