Re: [eigen] Polynomial solver, eigenvalues of companion matrix and balancing

[Manuel Yguel <manuel.yguel@xxxxxxxxx>]

Thanks for the hints Rohit.
And to be more precise I should have written that the polynomials were
"almost" not square free, but as they were generated randomly they
were very probably square free.
The cases that failed were due to very similar roots (with a
difference of less than 1.0e-4) which is exactly your point (b).

On Wed, Mar 17, 2010 at 5:18 PM, Rohit Garg <rpg.314@xxxxxxxxx> wrote:
> a) The companion matrix has a very special form, and reducing it to
> upper triangular matrix is a better way of finding eigenvalues.
> (givens rotations could be useful.)
>
> b) QR is not guaranteed to converge if atleast 2 eigenvalues have the
> same complex magnitude.
>
> On Wed, Mar 17, 2010 at 8:58 PM, Manuel Yguel <manuel.yguel@xxxxxxxxx> wrote:
>> Hello, I come again with the qr way of polynomial solving because the
>> Bezier bissection I am working on, only provide the real roots of the
>> polynomial.
>> It is interesting per se, but somebody might want the complex roots
>> too, so the qr way is still interesting.
>> Furthermore it will provide a concurrent solver to make comparisons.
>>
>> I have written balancing and tested the solver: the same behaviour appears.
>> So I checked what is going wrong and found two things:
>> 1) the problem shows up only for floats not doubles (do you have
>> experienced any particular problem with qr + float ?)
>> 2) for doubles the problem shows up when the polynomial is not square
>> free (i.e. with roots with multiplicity) as far as I have
>> investigated.
>>
>> Furthermore I made some comparisons with the GSL solver, which is only
>> provided for doubles (he, he ...) and the results are the same in term
>> of precision.
>>
>> What do you think of providing the solver like that with a warning
>> raised when it is instanciated with floats ?
>>
>> On the other hand, I am continuing working on the Bezier bissection
>> solver and the first step for this solver is to find the equivalent
>> square free polynomial (he he ^2), so I propose to provide this
>> functionality in general.
>>
>> If you agree, I will provide a patch for that module and add to the TODO:
>> - investigate why it fails so badly on floats (and fix it if possible),
>> - provide a qr algorithm adapted to the shape of the companion matrix
>> and possibly optimized for the particular case where we do not need
>> the eigenvectors, neither the Q matrix.
>>
>>
>> - best regards,
>>
>> Manuel
>>
>>
>>
>
>
>
> --
> Rohit Garg
>
> http://rpg-314.blogspot.com/
>
> Senior Undergraduate
> Department of Physics
> Indian Institute of Technology
> Bombay
>
>
>