From dpk Mon Dec 13 23:18:56 1993
Received: from bugs.npac.syr.edu by spica.npac.syr.edu (4.1/I-1.98K)
	id AA15603; Mon, 13 Dec 93 23:18:54 EST
Date: Mon, 13 Dec 93 23:18:54 EST
From: dpk (David P. Koester)
Message-Id: <9312140418.AA01723@bugs.npac.syr.edu>
Received: by bugs.npac.syr.edu (4.1/N-0.12)
	id AA01723; Mon, 13 Dec 93 23:18:52 EST
To: paulc@npac
Subject: activities report...
Status: R

Paul,

He is my activities report - it may a bit rough - but it has speedup
/efficiency numbers.

Dave

-------------------------------------------------------------
\documentstyle[11pt]{article}
\nonstopmode
\setcounter{secnumdepth}{5}
\setcounter{tocdepth}{5}
\renewcommand{\baselinestretch}{1.30}
\textwidth=6.5in
\textheight=8.5in
\topmargin=-0.5in
\oddsidemargin=0.25in

\begin{document}

\bigskip

\begin{center}
{\large \bf Activities Report for November --- December 1993} \\
{\large David Koester}
\end{center}
\bigskip

My activities for the November 1993 --- December 1993 reporting period has focused
on three areas:
\begin{enumerate}
\item developing a general block-diagonal-bordered form sparse Choleski solver
\item examining parallel dense matrix solvers for both Choleski factorization and general LU factorization with pivoting
\item generating block-diagonal-bordered form sparse matrices from any symmetric sparse matrix
\end{enumerate}
All efforts in these three areas support both my Ph.D. research and
the NPAC --- Niagara Mohawk contract.

I am presently developing implementations of parallel sparse
block-diagonal-bordered linear solvers for the Thinking Machines CM-5.
The implementation of current interest is a sparse
block-diagonal-bordered Choleski solver for symmetric positive
definite matrices, such as would be used to solve load-flow equations.
After examining the characteristics of real
block-diagonal-bordered power system matrices when examining matrix
orderings, it was obvious that the last diagonal block in the matrix
was not sparse, and dense factorization techniques would be more
efficient than sparse factorization techniques because dense
techniques can use vector/matrix BLAS that are optimized for memory
access and consequently optimized for performance.

I have examined efficient parallel dense factorization algorithms to
be used to solve the last block in block-diagonal-bordered sparse
power systems matrices.  Previous NPAC research into FORTRAN
benchmarks has been utilized to develop efficient parallel dense
matrix solvers for the last-block in sparse matrices.  I have
developed two implementations of dense matrix factorization on the
CM-5:
\begin{enumerate}
\item dense Choleski factorization for symmetric positive definite matrices
\item dense LU factorization for general matrices that require pivoting to ensure numerical stability.
\end{enumerate}
The software from NPAC did not include forward reduction and backward
substitution routines, triangular matrix solvers; consequently, these
parallel routines were also developed using similar block-pipelining
techniques as used in factorization.  In general, the same forward
reduction and backward substitution routines can be used for both
Choleski factorization of a dense positive definite matrix and the LU
factorization of a general dense matrix.  The only difference in the
implementations is that the backward substitution used with Choleski
requires a matrix transpose.  Due to the data distribution on various
machines, this step requires interprocessor communications.

These dense factorization implementations are complete, and have been
integrated with the software implementation for the sparse
block-diagonal-bordered Choleski solver.  This software is currently
being tested with generated data that has recursive
block-diagonal-bordered form.  Speed-up for these routines are good,
until processors (usually factoring the last block) are starved for
data.  Speedups in excess of 10 have been observed for 16 processors.
For two, four and eight processors, speedup for factorization is
nearly perfect, efficiencies equal to one.  A combination of a single
factorization, single forward reduction, and single backward
substitution always had efficiencies greater than 84%.  Efficiencies
for 16 processors generally decayed to less than 65%.

Also during this reporting period, the software to cluster real power
system networks has been augmented to generate block-diagonal-bordered
matrices suitable for use in the sparse matrix solver.  With these
modifications to the software, it will be possible to develop
simulated load-flow data that has the computational complexity of real
power systems.  The actual sparse matrix structure is used, with
random values for the data.  By carefully choosing these values, the
symmetric positive definite nature of these test matrices can be
ensured; consequently, there are no concerns for numerical stability.
This software can use either matrices from the Boeing-Harwell series
or power systems network data from Niagara Mohawk.  I prefer to use
matrices in the public-domain for my research, because of the fact
that others can attempt to duplicate my results.

\end{document}
\endinput





