To take advantage of the graphical nature of the spectral decomposition process, a graphical user interface (GUI) has been implemented for SDC. Written in C and based on X11R5's standard Xlib library, the Xt toolkit and MIT's Athena widget set, it has been nicknamed XI for ``X11 Interface''. When XI is paired with code implementing SDC we call the union XSDC.
The programmer's interface to XI consists of seven subroutines designed independently of any specific SDC implementation. Thus XI can be attached to any SDC code. At present, it is in use with the CM-5 CMF/CMSSL implementation and the Fortran 77 version of our algorithm (both of which use real arithmetic only). Figure 1 shows the coupling of the SDC code and the XI library of subroutines.
Figure 5: The X11 Interface (XI) and SDC
Basically, the SDC code calls an XI routine which handles all interaction with the user and returns only when it has the next request for a parallel computation. The SDC code processes this request on the parallel engine, and if necessary calls another XI routine to inform the user of the computational results. If the user had selected to split the spectrum, then at this point the size of the highlighted region, and the error bound on the computation (along with some performance information) is reported, and the user is given the choice of confirming or refusing the split. Appropriate action is taken depending on the choice. This process is repeated until the user decides to terminate the program.
All data structures pertaining to the matrix decomposition process are managed by XI. A binary tree records the size and status (solved/not solved) of each diagonal block corresponding to a spectral region, the error bounds of each split, and other information. Having the X11 interface manage the decomposition data frees the SDC programmer of these responsibilities and encapsulates the decomposition process. The SDC programmer obtains any useful information via the interface subroutines.
Figure 6: A sample xsdc session
Figure 6 pictures a sample session of xsdc
on the CM-5 with a matrix.
The large, central window (called the ``spectrum window'')
represents the region of the complex plane indicated by the axes.
Its title - ``xsdc :: Eigenvalues and Schur Vectors" -
indicates that the task is to compute eigenvalues and
Schur vectors for the matrix under analysis.
The lines on the spectrum window (other than the axes) are the result
of spectral divide and conquer, while the shading indicates that the ``bowtie''
region of the complex plane is currently selected for further analysis.
The other windows (which can be raised/lowered at the user's
request) show the details
of the process and will be described later.
The buttons at the top control I/O, the appearance of the spectrum window, and algorithmic choices:
The buttons at the bottom are used in splitting the spectrum. For example
clicking on Right halfplane and then clicking at any point on the
spectrum window
will split the spectrum into two halfplanes at that point, with the
right halfplane selected for further division.
This would signal the SDC code to decompose the matrix to
where the eigenvalues of
are the eigenvalues of
in the
right halfplane, and the eigenvalues of
are
the eigenvalues of
in the left halfplane.
The button Left Halfplane
works similarly, except that the left halfplane would
then be selected for further processing and the roles of
and
would be reversed.
In the same manner, Inside Circle and Outside Circle
divide the complex plane at the boundary of a circle,
while East-West Crosslines and North-South Crosslines
split the spectrum with lines at 45 degrees to the real axis (described below).
The Split Information window in the lower right
corner of Figure 2 keeps track of the matrix splitting process.
It reports the two splits performed to arrive at this current
(shaded) spectral region.
The first, an East-West Crossline split at the point 1.5
on the real axis, divided the entire complex plane into four sectors by
drawing two lines at 45 degrees through the point 1.5 on the
real axis. SDC decomposed the starting matrix into:
where the East and West sectors correspond to
the block
while the North and South sectors correspond to the
block.
Continuing in the East-West sectors as indicated by the previous split, that region is divided into two sub-regions separated by the boundary of the circle of radius 4 centered at the origin. The circle is drawn, making sure that its boundary only intersects the East and West sectors, and the matrix is reduced to:
The shading indicates that the ``bowtie'' region (corresponding to
the interior of the circle, and the block)
is currently selected for further analysis.
In the upper right corner of Figure 2 the Matrix Information window
displays the status of the matrix decomposition process.
Each of the three entries corresponds to a spectral region and a square
diagonal block of the block upper triangular matrix,
and informs us of the block's size, whether
its eigenvalues (eigenvectors, Schur vectors) have been
computed or not,
and the maximum error bound encountered along
this path of the decomposition process.
The highlighted entry corresponds to the shaded region and
reports that the
block contains 106 eigenvalues,
has been solved, and is in error
by up to
. The eigenvalues - listed in the window
overlapping the Matrix Information window -
can be plotted on the spectrum at the user's request.
The user may select any region of the complex plane (and hence
any sub-matrix on the diagonal) for further decomposition by
clicking the pointer in the desired region.
A click at the point on the imaginary axis for example,
would unhighlight the current region and shade the North and South sectors.
Since this region corresponds to the
block,
the third entry in the Matrix-Information window would be highlighted.
The Split-Information window would also be updated to detail
the single split performed in arriving at this region of the spectrum.
Once a block is small enough, the user may choose to solve it (via the Function button at the top of the spectrum window). In this case the eigenvalues, and Schur vectors for that block would be computed using QR (as per the user's request) and the eigenvalues plotted on the spectrum.
The current XI code supports real SDC only. It will be extended to handle the complex case as implementations of complex SDC become available.