Nonsymmetric eigenvalue problem

Nonsymmetric eigenvalue problem

[Lowell Johnson]

I notice that GSL doesn't (yet) support the computation of the eigenvalues 
of nonsymmetric matrices.  I've started converting my Fortran-based 
Mathieu function code over to C and ran into the symmetric eigenvalue 
limitation in GSL.

The matrix I need to solve is of the form

    a     -q                         0
   -2q   a-4    -q
          -q   a-16   -q
                      ...
                           ...      -q
    0                       -q   a-(2m)^2

Note that the only element making this matrix nonsymmetric is (2,1) (-2q).

For my original Fortran routines, I used the EISPACK routine RG(), which 
computes the eigenvalues and eigenvectors of a real, general matrix.  I 
was hoping to be able to use the GSL eigenvalue routines.  I have to 
determine the eigenvalues for four matrices.  The one listed above is the 
only nonsymmetric matrix.  The GSL routines work great for the other three 
matrices.

Any comments or suggestions?

Thanks.


    Lowell
-- 
---------0---------0---------0---------0---------0---------0---------0------
Lowell D. Johnson
ldj00@sio.midco.net

Linux:  Bringing stability, security, and freedom to home and business
        computing since 1991.  www.linux.org

Re: Nonsymmetric eigenvalue problem

[Brian Gough]

Lowell Johnson writes:
 > I notice that GSL doesn't (yet) support the computation of the
 > eigenvalues of nonsymmetric matrices.  I've started converting my
 > Fortran-based Mathieu function code over to C and ran into the
 > symmetric eigenvalue limitation in GSL.  For my original Fortran
 > routines, I used the EISPACK routine RG(), which computes the
 > eigenvalues and eigenvectors of a real, general matrix.  I was
 > hoping to be able to use the GSL eigenvalue routines.  I have to
 > determine the eigenvalues for four matrices.  The one listed above
 > is the only nonsymmetric matrix.  The GSL routines work great for
 > the other three matrices.
 >  Any comments or suggestions?

The algorithm for non-symmetric eigenvalues is very complicated, which
is why it wasn't implemented.  Maybe there is a simpler algorithm for
handling tridiagonal nonsymmetric matrices though.

What method does Fayez Alhargan use in the TOMS papers?

Re: Nonsymmetric eigenvalue problem

[Lowell Johnson]

On Wed, 14 Aug 2002, Brian Gough wrote:

> Lowell Johnson writes:
>  > I notice that GSL doesn't (yet) support the computation of the
>  > eigenvalues of nonsymmetric matrices.  I've started converting my
>  > Fortran-based Mathieu function code over to C and ran into the
>  > symmetric eigenvalue limitation in GSL.  For my original Fortran
>  > routines, I used the EISPACK routine RG(), which computes the
>  > eigenvalues and eigenvectors of a real, general matrix.  I was
>  > hoping to be able to use the GSL eigenvalue routines.  I have to
>  > determine the eigenvalues for four matrices.  The one listed above
>  > is the only nonsymmetric matrix.  The GSL routines work great for
>  > the other three matrices.
>  >  Any comments or suggestions?
> 
> The algorithm for non-symmetric eigenvalues is very complicated, which
> is why it wasn't implemented.  Maybe there is a simpler algorithm for
> handling tridiagonal nonsymmetric matrices though.
> 
> What method does Fayez Alhargan use in the TOMS papers?

I've taken a very cursory look at Alhargan's algorithm and it appears to
use at least some of the same methods that I've used.  I'm not a member of
SIAM or ACM, and the accessible technical library doesn't carry much in 
the way of math journals, so I don't have ready access to the actual 
paper.  But I have downloaded Alhargan's C++ routines.

The biggest difference appears to be (and this is something that I hadn't
really  given much thought to yet) that I use the recurrence relation
matrices to solve for multiple characteristic values in one pass, whereas
it appears that Alhargan's method computes a single characteristic value
at a time.

Since my original work required Mathieu functions of many orders, it made
sense to compute all characteristic values at once, storing them in an
array.  But this method may be costly for requests only requiring a single
value.

So maybe I'll work on combining the two approaches in some way.

Regarding the nonsymmetric eigenvalue issue, I've found a routine in
EISPACK (FIGI2) that converts a sign-symmetric tridiagonal matrix into a
symmetric tridiagonal matrix.  The algorithm looks pretty simple, so I'll
try to get it going.

Thanks.


    Lowell
-- 
---------0---------0---------0---------0---------0---------0---------0------
Lowell D. Johnson

Linux:  Bringing stability, security, and freedom to home and business
        computing since 1991.  www.linux.org

Re: Nonsymmetric eigenvalue problem

[Brian Gough]

Lowell Johnson writes:
 > I've taken a very cursory look at Alhargan's algorithm and it
 > appears to use at least some of the same methods that I've used.
 > I'm not a member of SIAM or ACM, and the accessible technical
 > library doesn't carry much in the way of math journals, so I don't
 > have ready access to the actual paper.

Luc Maisonobe writes:
 > The rksuite comments say this method is described in this paper :
 >    High Order Embedded Runge-Kutta Formulae P.J. Prince and
 >    J.R. Dormand J. Comp. Appl. Math.,7, pp. 67-75, 1981
 > I would be VERY interested if someone could provide me a copy of
 > this article (just email me directly to have my postal adress).

I will add to the list of tasks:

  * Volunteers with access to a good library to get copies of papers 
    for other developers.

If anyone is able to do that it would be a very useful way to help the
project, without involving too much work.

Email me privately and I will coordinate.

Thanks,
Brian

Re: Nonsymmetric eigenvalue problem

[Brian Gough]

Lowell Johnson writes:
 >  Since my original work required Mathieu functions of many orders,
 > it made sense to compute all characteristic values at once, storing
 > them in an array.  But this method may be costly for requests only
 > requiring a single value.

The bessel function rountines come in two versions, one for computing
a single order, and an '_array' function for computing a range of
orders simultaneously.  For general numerical use the single order
functions would be the first priority though.