Re: Roots of polynomials

[Benjamin Abbott]

On Apr 17, 2013, at 6:49 AM, Urs Hackstein <address@hidden> wrote:

> Hello,
> 
> there exists a built-in function "roots" which computes the roots of a given 
> polynomial. How does octave computes these roots? This function is pretty 
> fast, but are there faster functions doing the same? We have to compute the 
> roots of a huge number of polynomials in our program, thus this could 
> minimize the runtime.
> 
> Or are there faster algorithms in the case that we aren't interested in all 
> roots, but only in a special root whose real part is already known?

The roots are found by constructing a matrix whose characteristic polynomial is 
a scaled version of the polynomial in question.

The eigen values of that matrix are the roots of the polynomial.

For the general case, this is the fastest approach.  For your case a direct 
search along the imaginary part of the root may be faster.

Ben