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

[ Thread Index | Date Index | More Archives ]

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

Senior Undergraduate
Department of Physics
Indian Institute of Technology

Mail converted by MHonArc 2.6.19+