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