Re: Roots of polynomials

[Urs Hackstein]

But how can such a direct search along the imaginary part of the root be done? I tried to compute the integral \int_\alpha (f'/f )s over a curve \alpha surrounding the root, but this is still slower than the roots routine.

2013/4/17 Benjamin Abbott <address@hidden>

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