\section{Introduction}
\label{sec:intro}
\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 
typically has two to five degrees of freedom;
\BS\ is designed to take advantage of problems with this type of
local structure.
\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\ is general purpose;
we require only that the matrices be sparse and 
symmetric in structure (but not necessarily in 
value).\footnote{Whenever we use the term {\em nonsymmetric}
with respect to \BS, we mean symmetric in structure and nonsymmetric 
in value.  Thus, \BS\ handles most matrices
arising in finite-element calculations; however,
it cannot handle general nonsymmetric matrices.}
\sindex{symmetric matrix}
\sindex{nonsymmetric matrix}

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

\vspace{-.06in}
\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.

\vspace{-.06in}
\item \BS\ runs on a variety of parallel architectures and can easily be
ported to others.
The MPI message-passing standard \cite{MPI:book,MPI:standard}
is used to achieve portability across architectures.
\sindex{MPI}
Machines on which \BS\ has been tested include
the IBM SP series, the Cray T3D and T3E, the
SGI Cray Origin2000, the HP-Convex Exemplar, the Intel Paragon,
and networks of Sun, SGI, DEC alpha, and HP workstations.
The {\tt bmake} directory contains contains a complete 
set of the machine-dependent makefiles for the architectures
currently supported.

\vspace{-.06in}
\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
orderings and the scalable performance of the linear solver
described below.
\sindex{graph coloring}

\vspace{-.06in}
\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\ uses 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}Effective use of total memory by \protect\BS}
\begin{center}
\noindent
\begin{tabular}{|l|c|c|l|l|} \hline
          &            &                    & Memory per  & Total  \\
          &            & Number of          & Processor   & Memory \\
          & Number of  & Matrix             & (Usable   & (Usable \\
Machine   & Processors & Nonzeros           & Memory)   & Memory)\\
\hline 
Intel       &     &                    & ~16 MBytes   &  ~8 GBytes  \\ 
DELTA       & 512 & $1.9\times 10^{8}$ & (11 MBytes) &  (5.6 MBytes) \\ \hline
IBM SP1     & 128 & $5.1\times 10^{8}$ & 128 MBytes &  16 GBytes \\\hline
\end{tabular}
\end{center}
\end{table}
\sindex{memory}

\vspace{-.06in}
\item The software is designed to achieve scalable performance.
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 MFlops to 3.83 MFlops when
the number of processors was increased from 128 to 512.
\sindex{scalable performance}

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

\vspace{-.06in}
\item The software is a general-purpose sparse solver.
Hence, \BS\ is effective also 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}.
\sindex{unstructured meshes}

\vspace{-.06in}
\item The software requires minimal input.
You 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.

\vspace{-.06in}
\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
in this situation.
\sindex{multiple right-hand sides}

\end{itemize}

The remainder of this manual is organized as follows.
We begin in \S\ref{sec:algorithms} with a brief description of
the algorithms used in \BS.
In \S\ref{sec:context}, \S\ref{sec:data}, and \S\ref{sec:main}
we present the routines required to set up the context and
matrix data structures and solve linear systems with \BS.
In \S\ref{sec:misc} we discuss a number of details dealing
with flop counting, BLAS performance, message-passing options,
and other issues that arise in tuning the performance of 
an application.
The installation and availability of \BS\ are
discussed in \S\ref{sec:install}, and in 
\S\ref{sec:examples} we describe the program
examples that are included with this version.
Finally, in \S\ref{sec:plans} we discuss related software and
plans for future versions of the code.

This document is intended to be used primarily as a reference.
If you are a new user, we recommend using the \BS\ 
examples as templates for your application codes.

\newpage
