Version 1.2.1 --------------- ScaLAPACK implementation of Spectral Divide and Conquer (SDC) ================================================================= What is SDC? ============= Briefly, SDC is used to compute eigenvalues, eigenvectors, and Schur vectors of nonsymmetric matrices. It is built almost entirely of calls to ScaLAPACK/PBLAS/LAPACK/BLAS routines for matrix inversion, matrix multiplication and QR decomposition, and so is as fast and scalable as these underlying routines. The algorithm works by repeatedly dividing the complex plane (under user control) into regions containing the eigenvalues of interest to the user. Only those parts of the complex plane containing interesting eigenvalues need to be analyzed. Here is an example. For the 200 x 200 Brusselator matrix, the task is to find the rightmost cluster of eigenvalues (where they bifurcate from real to complex pairs). It is known that most of the eigenvalues, as well as these interesting ones, have negative real parts. Armed with this information and more, the user might suspect that the interesting eigenvalues all have real part greater than, say, -50. So using SDC, he would first "split" the spectrum at the line x=-50. This decomposes the original matrix into 2 x 2 block upper triangular form: 30 170 30 [ A11 A12 ] 170 [ 0 A22 ] where A11 contains all the eigenvalues (30 of them) with real part greater than -50 (in the halfplane to the right of x=-50) and A22 contains all the rest (in the halfplane to the left of x=-50). The user may now go on to further subdivide A11 (or A22) into smaller parts, or invoke a standard algorithm if the block is small enough. Implementation details ========================= Subroutine PDSDC is the driver for computing the Schur decomposition and all the eigenvalues for a non-symmetric matrix. It uses routines PDHALFP to repeatedly divide the complex plane along lines parallel to the complex axis, which in turn uses PDGESGN to compute the matrix sign function and PDSGNDFL to deflate the matrix as described above. The subroutines use several pre-release versions of ScaLAPACK routines that have been modified to support 'full-index' access. They have been suffixed with a '0' to avoid confusion (e.g. PDGEMM -> PDGEMM0). Thanks to Antoine Petitet (petitet@cs.utk.edu). Note: A release using the newer 'full index' subroutines (soon to be a part of the main ScaLAPACK release) is under development. Organization =============== SRC/ contains the core routines to implement SDC TESTING/ routines to test SDC (under development) README this file Building the Software ======================== There is a Makefile in the SRC directory. It is configured to build a library of the SDC routines, which you may include when linking to other code. The TESTING directory also contains a Makefile for building an executable for performing simple tests. Note that these Makefiles assume a 'standard' Scalapack/lapack/blas distribution and may have to be tweaked to fit into your enviromnent. Miscellaneous ================ Much of the debugging code remains since we are still in the development stages. We have tried to hillight these wherever possible in our codes; hopefully this will not generate confusion. I anticipate that this code will be updated fairly regularly as other scaling schemes are added and bugs are resolved. Please contact the authors directly for latest developments. The web page "http://www.cs.berkeley.edu/~hbr/sdc" will chronicle the latest developments. An X-window interface is available for SDC; it will be made available in a future release. This interface is perhaps the most suitable as it gives the user complete control over the division process and displays the spectrum with eigenvalues, Gershgorin disks, etc. Howard Robinson hbr@cs.berkeley.edu http://www.cs.berkeley.edu/~hbr James Demmel demmel@cs.berkeley.edu http://www.cs.berkeley.edu/~demmel Computer Science Division University of California Berkeley, CA 94720 http://www.cs.berkeley.edu