\section*{Software Description}
The major obstacle to the successful solution of many large-scale
scientific and engineering problems on massively parallel computers
is the lack of efficient software for sparse matrix solution.
The software package \BS\ has been developed to answer this need.

\BS\ is a scalable parallel software library primarily intended for 
the solution of sparse linear systems that arise from physical 
models, especially problems involving multiple degrees of freedom
at each node.  
For example, when the finite element method is used
to solve practical problems in structural engineering, each node will
typically have anywhere from 2 to 6 degrees of freedom associated with it;
\BS\ is designed to take advantage of problems with this local structure.
However, \BS\ is also reasonably efficient for problems that have only
one degree of freedom associated with each node, such as the
three-dimensional Poisson problem.
\BS\ does not require that the matrices have any particular
structure other than being sparse and symmetric.

\section*{Features and Performance}

\BS\ has incorporated several unique features that allow
efficient performance on diverse parallel architectures.
We have summarized these features below:

\begin{itemize}

\item Every aspect of the linear system solution---the computation
of a matrix ordering, the renumbering, the computation of the
preconditioner, and the iterative solution---is done in parallel.

\item The software uses an efficient implementation of the 
parallel coloring algorithm described in \cite{jp:pcolor}
that allows for the efficient computation of matrix
ordering and the scalable performance of the linear solver
described below.

\item The software is designed to solve linear systems whose sizes are 
the same order as the total amount of memory available on a parallel
machine.  For example, Table~\ref{tab:mem} shows how
effectively \BS\ is able to use the available memory on two
different architectures for the high-temperature superconductor
modeling application described in \cite{jp:super}.
Note that some of each processor's memory is used by the operating system
and program executable (e.g., approximately 4 MBytes and 1 MByte
respectively on the Intel DELTA).
For this application an unpermuted version of 
the matrix is maintained in addition to the memory required by \BS.
Moreover, the memory required to store {\em only} the indices and the
double-precision values for $1.0\times 10^{8}$ nonzeros is 1.2 GBytes.
\begin{table} [htb]
\caption{\label{tab:mem}The effective use of total memory by \protect\BS}
\begin{center}
\noindent
\begin{tabular}{|l||l|l|l|l|} \hline
          & Number of  & Number of          & Memory per  & Total  \\
Machine   & Processors & Matrix Nonzeros    & Processor   & Memory \\
\hline \hline
Intel DELTA & 512 & $1.9\times 10^{8}$ & 16 MBytes  &  8 GBytes \\ \hline
IBM SP1     & 128 & $5.1\times 10^{8}$ & 128 MBytes &  16 GBytes \\\hline
\end{tabular}
\end{center}
\end{table}

\item The software is designed to achieve scalable performance.
That is, with a constant number of unknowns per processor, a matrix
nonzero structure resulting from local graph connections (the
usual case with any finite element mesh), and a reasonable
partitioning of vertices to processors, the average processor
performance is roughly constant.
For example, for the piezoelectric crystal modeling application
described in \cite{jp:bell_prize}, the average processor performance
on the Intel DELTA varied from 4.16 megaflops to 3.83 megaflops when
the number of processors was increased from 128 to 512.

\item The software is designed to use Level 2 and Level 3 dense BLAS
to achieve efficient use of processors on different architectures.
For example, for the application described in \cite{jp:super}.
Table~\ref{tab:perf} shows the average processor performances.
Note that a significant percentage of the maximum double
precision performance is achieved
for a {\em sparse} matrix calculation
on these very different processor architectures.
\begin{table} [htb]
\caption{\label{tab:perf}The efficient use of different processor
architectures by \protect\BS}
\begin{center}
\noindent
\begin{tabular}{|l||l|l|l|l|l|} \hline
          &              & Number     & Avg.\ Proc.   & \\
          & Processsor   & of         & Performance   & Total \\
Machine   & Architecture & Processors & Achieved      & Performance \\
\hline \hline
Intel DELTA & Intel i860  & 512       & 8.33 MFlops    & 4.26 GFlops   \\ \hline
IBM SP1     & RS 6000/370 & 128       & 20.5 MFlops    & 2.62 GFlops \\ \hline
\end{tabular}
\end{center}
\end{table}

\item The software is a general-purpose sparse solver---\BS\ is
effective on problems arising from unstructured meshes.
For example, a total performance of 2.2 GFlops was achieved
on 512 processors of the Intel DELTA for an adaptive mesh
calculation using high-order shell elements in a three-dimensional
geometry \cite{jp:olaf}.

\item The software requires a minimal amount of input from the
user.  The user must give \BS\ the matrix nonzeros and global
indices of rows corresponding to the unknowns assigned to each
processor and the mapping functions to translate between global
and local indexing.
%A novel feature has been incorporated in \BS\ to make this
%indexing easier for problems where the number of rows per processor
%is initially unknown or may vary:  the global numbering does
%not need to be contiguous.
%This feature allows the user to use the maximum number of unknowns
%that any processor may store, say $n_{\max}$, and the processor
%number {\it my\_id} to compute the an offset {\it my\_id}$\times n_{\max}$.
%This offset can be added to local indices to achieve a unique 
%global numbering that can also allow for very simple translation
%functions.

\item \BS\ is designed to be most effective within real application codes.
In our experience, most application codes must solve the
same linear systems with several different right-hand sides and/or solve
linear systems with the same structure, but different matrix values,
multiple times.  \BS\ has, therefore, been designed to work well
within this context.

\end{itemize}

