Re: unsymmetric eigenvalue update

[Patrick Alken <patrick.alken@colorado.edu>]

Thanks for the update. I have a new balance and hessenberg
routine too that I fixed up a while back. Its no longer necessary
to do any dynamic allocation for the hessenberg function.
I also modified the francis routine a little more to
work better on ill-conditioned matrices and reduce more roundoff
error. Also, I modified linalg.texi and eigen.texi to give
complete documentation on all the functions I've added.
I will make a new patch against the latest CVS and post it as soon as
I can.

An update regarding the high-performance eigensolver: I've
been working on implementing the high-performance small bulge
aggressive early deflation method, and currently have a completely
working code. Unfortunately, the performance is currently about
twice as slow as the fortran version which is going to be in the
next lapack release. I already made gsl_matrix_{get,set} macros
and disabled range checking which resulted in about a 30% speed
improvement. I also made optimized versions of the householder
transform routines specifically for 3-by-1 vectors, but it still
does not match the speed of the fortran version. I am still
investigating why.

Another issue here is that I had to port about 4 lapack routines
over to GSL to get the high-performance eigensolver to work.
Plus the code for the eigensolver is heavily based on the fortran
code which will be in lapack. I know there have been discussions
on this list in the past regarding lapack licensing issues and
I confess I don't fully understand whether it is acceptable/legal for
GSL to contain lapack ported code.

Due to the sheer amount of code needed to get the high-performance
eigensolver to work (currently about 4500 lines) mainly due to
the large lapack routines, I'm starting to wonder if its worth it.
Most of this code is only useful in terms of the eigenvalue problem
and won't be useful for more general linear algebra problems. So
all this code is there for just solving one problem and it might
be wiser to go with the simpler francis solver whose code would
be easier to understand/maintain. The rest of GSL seems to have
the goal of containing small and simple to understand algorithms
and all of this lapack code might just "uglify" the library. Any
comments on this?

Patrick Alken

On Mon, Aug 14, 2006 at 03:24:08PM +0100, Brian Gough wrote:
> At Tue, 13 Jun 2006 09:56:20 -0600,
> > I propose adding the double-shift method to gsl (assuming it
> > passes any further tests needed) which would be a perfectly
> > fine eigenvalue solver (EISPACK used it for a number of years)
> > until I (or someone else) can find the time to implement method 3.
> > 
> > Attached is the latest (final? :)) patch.
> 
> The latest patch is in sources.redhat.com CVS with some extra
> cleanups.  It works well.  I modified the balance() routine to return
> the diagonal scaling elements D (for computing the eigenvectors later)
> and moved the memory allocation up out of hessenberg() into the
> workspace.
> 
> -- 
> Brian Gough
>