This is the mail archive of the gsl-discuss@sourceware.org mailing list for the GSL project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
Hi all, After reviewing the LAPACK and EISPACK eigenvalue routines, I've changed my convergence criteria to declare failure after 30*N iterations. My original number of 30 was based on the Numerical Recipes algorithm, which I now see was copied from the EISPACK algorithm but with a typo of 30 instead of 30*N. I have run my code through Brian Gough's test program on 12x12 and 200x200 random matrices, as well as some integer matrix cases and find no significant disagreement with LAPACK. For those who expressed concern earlier about speed issues, I'd like to share some things I found while studying this problem: 1) In 1962 the Francis double-shift QR algorithm was published which typically converges in about 8n^3 flops if you only want eigenvalues. This is the algorithm which was implemented in EISPACK (hqr.f) and is also implemented in LAPACK as DLAHQR. Also this is the algorithm discussed in Golub & Van Loan and is presented in Numerical Recipes (which is just the EISPACK hqr routine converted to C). 2) In 1989, Bai and Demmel published their multi-shift QR algorithm and gave some numerical tests showing that it is generally faster than hqr from EISPACK. However they say its too complicated to derive an approximate number of flops required for the general problem. Furthermore, the multi-shift algorithm needs to call the double-shift algorithm to calculate the shifts. So it is impossible to dispense with the double-shift algorithm. This algorithm is implemented in LAPACK as DGEES (DGEES calls DLAHQR to get the shifts) 3) In a further significant development, in 2001 a multishift QR algorithm was proposed in the papers K. Braman et al, "The Multishift QR Algorithm: Part I: Maintaining Well Focused Shifts" and K. Braman et al, "The Multishift QR Algorithm: Part II: Aggressive Early Deflation" which introduces a way to deflate eigenvalues much more quickly than the standard test used in the previous two methods. The numerical results in these papers are very impressive and show convergence with far less flops than the LAPACK algorithm. Subsequent papers have extended this method to the QZ algorithm of the generalized eigenvalue problem, and as far as I can tell, this aggressive deflation method is considered the best QR algorithm currently available. If any experts are reading this please correct me! So, the code in my gsl patch is equivalent to the HQR routine in EISPACK, which has perfectly fine accuracy but is not the fastest converging. I believe ultimately, the goal should be to implement method #3 which will perform better than LAPACK's DGEES, but is fairly complex and will take me some time to learn/implement. Furthermore, the implementation of methods 2 or 3 require the double-shift method 1 anyway, so it was not a waste of time to code up the double-shift method. 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. Patrick Alken
Attachment:
gsl.unsymm.patch
Description: Text document
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |