| Re: [eigen] Polynomial solver, eigenvalues of companion matrix and balancing |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Polynomial solver, eigenvalues of companion matrix and balancing
- From: Rohit Garg <rpg.314@xxxxxxxxx>
- Date: Wed, 17 Mar 2010 21:48:23 +0530
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :from:date:message-id:subject:to:content-type; bh=fBD4BWiL264PcdGxA3NSwbsCaTT0FVru9fLNpCp7Xc0=; b=O7Js42UNb/42MmWxbUEsCQoGJmrFviQWaHzvvBpj2enGv8S6Qowy9PhHum3s6zXwmI 1RjfGfuBa7jVaVtAwqOMgrDys2w/pTFyFNPykDK6C9FMnGOXNioyfNwVyCOXbdeQPB7W I7gpOCT3H9sXV+96gwGf1EnLIGO8c2D9/jX1A=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; b=HvGKDrYOvh0hncFIlf9K0r/hHxYV/ClFS1K49IYx5r87/6O355XzkvdpkqvZx1XodC /ARB+CV29cWxuX/e/W5w6UO0Zt42Ou+llkYvMhgLnL+oUSGCPefPJjq4YQOPJlyGYSV3 1HdzZGCO0MccmHwLL5KtEpM/rWi8Uq/lUrhdo=
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