Subject: mail conversation with M. Heath

From: dpk (David P. Koester)
Date: Wed, 3 Mar 93 12:57:27 EST

My mail to M. Heath:
-----------------------------------------------------------------------

Micheal Heath,

I am a Ph.D. candidate working for Geoffery Fox and Sanja Ranka.
My research proposal is "Parallel Direct Sparse Matrix Techniques 
for Power Systems Applications".  In particular, I am looking at 
parallel direct techniques to solve non-symetric sparse matrices
resulting when solving the Differential-Algebraic equations in
the power systems transient stability problem.  There is a natural
block-bordered structure in much of the matrix (the differential
equations representing the electrical power generators) and the 
electrical network can also be reordered into block-bordered form.

Geoffery has told me that you have obtained speedups on the order
of 1.5 for every time you double the number of processors.

I was wondering if I could examine your code, so that I could get some
pointers on improving my code, and I was wondering if you had a
data set that I could use to compare speedup to your software.

To date, I have only tested my software on generated data.  I have
real data from a local power company, however, I want to get an
idea on how my software compares to your's (I am told that it is
some of the best available!)

I am in the software implementation phase of my research, and I have a direct
solver running on the CM-5 and I have developed some graph cluster 
identification software to partition graphs into block-bordered
diagonal form.  This software includes a symbolic factorization
routine, and X-windows support for matrix structure visualization.

After having examined your paper in "Parallel Algorithms for
Matrix Computations" and numerious papers by authors came to be known
as the "Gang of Four" (A. George, J. Liu, E. Ng, and you), I believe
that my block-bordered diagonal software may be applicable to many 
sparse matrices that have appropriate elimination trees.  My software
has basically no task graph - only the locations of the non-zeros in the 
last block are required at each parallel processor.  Presently, I am treating 
this block as being sparse, but I am examing the sparsity structure
to determine whether it would be more appropriate to use explicit data 
structures and treat this portion of the matrix as dense.  

I would appreciate hearing from you, and I would also appreciate seeing
your software and having an opportunity to test my software on your
data.

David Koester

Phone: 315 - 336-4966 (work - 7:30-2:30 EST)
       315 - 443-9182 (school - 4:00-11:00 EST)

E-mail: [email-masked]

-----------------------------------------------------------------------

Micheal Heath's response
-----------------------------------------------------------------------

>From [email-masked] Wed Mar  3 11:02:46 1993
Date: Wed, 3 Mar 93 10:03:21 CST
From: [email-masked] (Michael Heath)
To: [email-masked]
Subject: Re:  Sparse Matrix solvers
Status: R

Thanks for your note.  I would be very interested in taking a closer
look at your work if (or when) you have a write-up you can send me.
My current work in this area has been done in collaboration with Padma
Raghavan, who is a postdoctoral research associate working with me.
In particular, Padma has been writing and maintaining the code, so you
would need to talk with her about obtaining it.  The code is still
under development and its diverse parts have not yet been fully
integrated, so she may not feel ready to distribute it at this point.
You can contact Padma by email at the address [email-masked].

The major thrust of our work since my survey paper (SIAM Review,
September 1991) has been on doing the whole problem in parallel, not
just the numeric parts.  In particular, we do the ordering and other
symbolic computations in parallel on distributed-memory machines, as
well as the factorization and triangular solution.  We have written
some tech reports on this work that we could send you.  It sounds like
the flavor of your work is very different from ours, so they might be
hard to compare.  Our primary application target has been finite
element structural analysis, but it would be very interesting to try
our code on electrical power problems if we could get some of those
from you, both artificially generated and real.

The preliminary performance numbers that I mentioned to Geoffrey at a
conference last year were for the ordering phase only, since that is
all we had completed at the time.  We have now finished a preliminary
implementation of all phases of the computation, both symbolic and
numeric.  The performance varies, naturally, with problem size and
other problem characteristics.  And in a sense we haven't really given
the code a true test yet, since we have not had access to large enough
problems to utilize large numbers of problems effectively.  So, I think
it is fair to say that we are reasonably pleased with the performance
we are seeing thus far, given the limited size and variety of test
problems we have access to, but are hopeful that things will be better
still for truly "grand challenge" scale problems.

-Michael Heath