|Re: [eigen] Polynomial solver, eigenvalues of companion matrix and balancing|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Polynomial solver, eigenvalues of companion matrix and balancing
- From: Manuel Yguel <manuel.yguel@xxxxxxxxx>
- Date: Wed, 17 Mar 2010 19:44:09 +0100
- 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=AgQjAmjhyjAIrzp5zj2xwoiuI9P8BaWxuH2Nz/IJY+s=; b=DZK+cL5ZqSL2wRa1YA0UL5R3qynZcYemRc0RAwuQA1STVfgzq/OE7lRQ9IGaxiVpQF LJOyc9Nwuyi+qModicbk7cRYlvNvuQ06ccc9HQUlg1muGSv+GquiJtllA8BNvRmfNitG QQrFLHy5/XQ+PFWXBSPTU3kRkykcpL1w3DiuY=
- 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=Y/JetOpc4KBI5Y00WTizx2GvvpCOLX2bVkoWO2k7tMsvSnbYpR7SXFEGd3J9DObiuj 31KwVC1ulRNYOSgMBe0UAWwhcRgL2ocRx9+FDyKqJY6oiI/H/xLyGTRlFvoUqxgIKhVI dbbeZhwT3+jTj3pgSjdbFJUu9kOaFknr57kfQ=
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
>> 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
>> 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,
> Rohit Garg
> Senior Undergraduate
> Department of Physics
> Indian Institute of Technology