\section{The User Matrix Data Structure {\tt BSspmat}}
\label{sec:data}
To pass your matrix to \BS, you must use the matrix data
structure {\tt typedef BSspmat}\findex{typedef BSspmat}.
Given this data structure, \BS\ will convert the matrix
to a \BS\ internal data structure of 
{\tt typedef BSpar\_mat}\findex{typedef BSpar_mat} in the routine
{\tt BSmain\_perm()}\findex{BSmain_perm()} (we discuss
this routine in detail in \S\ref{sec:main}).
In this section we describe two approaches for converting
sparse matrix data into the {\tt BSspmat} format.
The first, using the routine {\tt BSeasy\_A()}, is 
recommended and should be fairly painless starting with
most standard sparse matrix storage schemes.
The second, directly inserting the data and mappings into 
the structure {\tt BSspmat}, allows for greater flexibility
but is more complicated.

\subsection{The Easy Way to Convert Your Data to {\tt BSspmat}}

We recommend that you use, if possible, the routine
{\tt BSeasy\_A()} to generate the {\tt BSspmat} data structure.
The following are the essential data that you must specify
for {\tt BSeasy\_A()}.\findex{BSeasy_A()}
\begin{itemize}

\item The matrix rows must be partitioned onto processors
such that each processor has at least one row, each row
has a unique global number, and each row is assigned to
a unique processor.

\item The global row numbers
assigned to each processor must be contiguous.\footnote{This
limitation applies only to {\tt BSeasy\_A()}.  \BS\
itself does not require that row numbers be contiguous;
an arbitrary row mapping can be used.}
If processor $p$ is assigned $n_p$ rows,
and the rows numbers start at $i_p$, the rows assigned
to processor $p$ must be
$i_p, i_p + 1, \ldots, i_p + n_p - 1$.
For example, if there are two processors, processor $0$
could have rows $0,1,2$ and processor $1$ could have
rows $4,5,6$ but not rows $4,6,7$.
Note that the global row numbering can skip numbers;
in the above example we did not use the row value $3$.

\item The nonzero structure and matrix values for the
rows assigned to each processor must be given in the
three arrays {\tt rp}, {\tt cval}, and {\tt aval}.
The storage format for these arrays corresponds to the
standard compressed row storage (CRS) scheme for sparse matrices.
See pages 58--69 of \cite{template} for
a detailed discussion of various sparse storage schemes.
Each processor uses the {\em local} numbering of its
rows $0,1,\ldots,n_p-1$ to index these arrays.
The first array {\tt rp} is an index of pointers into the 
two other arrays indicating where the global column numbers
and nonzero values for each row begins.
Thus, the $i$th row has nonzeros in columns
{\tt cval[rp[i]], cval[rp[i]+1],...,cval[rp[i+1]-1]}.
The nonzero values are given in corresponding locations
in the array {\tt aval}.
The column values for each row in the array
{\tt cval} must be sorted from lowest to highest.
Note that the entire matrix row must be represented
in these arrays even if the matrix is symmetric.
\end{itemize}

Given this data, the routine {\tt BSeasy\_A()}\findex{BSeasy_A()}
can be called by each processor to generate the 
{\tt typedef BSspmat}\findex{typedef BSspmat} data structure.
The function arguments for {\tt BSeasy\_A()} are as follows.
\begin{verbatim}
  BSspmat *BSeasy_A(int start_num,int n,int *rp,int *cval,
                    FLOAT *aval,BSprocinfo *procinfo);
\end{verbatim}
Note that {\tt start\_num} is the starting global row number ($i_p$
in the above example), and {\tt n} is the number of rows
assigned the processor ($n_p$ in the above example).

To illustrate the information {\tt BSeasy\_A()} requires, 
we consider the following $4\,\times\,4$ matrix:
\begin{equation}
\label{eqn:crs}
A = 
\left(
\begin{array}{cccc}
a & b & 0 & 0\\
c & d & e & 0\\
0 & f & g & h\\
0 & 0 & i & j
\end{array}
\right) ~~.
\end{equation}
Let the global numbering of the rows and columns of the matrix
be $0$ to $3$ (e.g., $A_{12} = e$).
Suppose that we have two processors, 0 and 1,
and that we assign rows $0$ and $1$ of the matrix 
to processor $0$ and rows $2$ and
$3$ to processor $1$.
Given this distribution of the rows of the matrix and the
global numbering of the columns, we would have the arrays
{\tt rp}, {\tt cval}, and {\tt aval} as shown in
Figure~\ref{fig:crs}.
When processor $p$ calls {\tt BSeasy\_A()}, its value of
{\tt start\_num} would be given by $i_{p}$ and its value
of {\tt n} would be $n_{p}$.
\begin{figure} [htb]
   \centerline{
		\hbox{
		\psfig{figure=crs.ps,height=2.5in}
	  }
 }
\caption{The values of the arrays $rp$, $cval$, and $aval$
for the matrix given in equation~\protect{\ref{eqn:crs}}.
The matrix is partitioned so that processor $0$ is assigned
rows $0$ and $1$ and processor $1$ has rows $2$ and $3$.
Note that indexing of the arrays and the matrices rows 
and columns begins with 0.}
\label{fig:crs}
\end{figure}

\subsection{The Advanced Way to Convert Matrix Data to {\tt BSspmat}}
You can also allocate the {\tt BSspmat} without using
{\tt BSeasy\_A()}.
Although this approach requires a bit more work, it can be more flexible.
For example, we had no difficulty in writing a C interface routine
to take a matrix written in a standard sequential format by a Fortran
code and put this structure around it without duplicating the data
in the Fortran sparse matrix.

Within the {\tt BSspmat} data structure, each row of the matrix
is represented by the structure {\tt typedef BSsprow}.
\findex{typedef BSsprow}
The data structures are specified as follows:

{\footnotesize
\begin{verbatim}
  typedef struct __BSsprow {
      int diag_ind;   /* index of diagonal in row */
      int length;     /* num. of nz in row */
      int *col;       /* col numbers */
      double  *nz;    /* nz values */
  } BSsprow;

  typedef struct __BSspmat {
      int num_rows;       /* number of local rows */
      int global_num_rows;/* number of global rows */
      int symmetric;      /* if TRUE, the matrix should be symmetric */
      int icc_storage;    /* if TRUE, storage scheme used for ICC preconditioner */
                        /* if FALSE, ILU storage scheme used */
      BSmapping   *map;   /* mapping from local to global, etc */
      BSsprow **rows;     /* the sparse rows */
  } BSspmat;
\end{verbatim}
}

First, we discuss the structure {\tt BSspmat}.\findex{typedef BSspmat}
The field {\tt num\_rows}
contains the number of rows local to the processor.
The field {\tt global\_num\_rows} contains the total number
of rows in the linear system.
The fields {\tt symmetric} and {\tt icc\_storage} respectively
indicate whether the matrix is symmetric and whether an incomplete
Cholesky factorization will be computed.
The field {\tt map} contains mapping information that will
be discussed later.  The field {\tt rows} is an array of pointers to
local rows of the sparse matrix.

In the structure {\tt BSsprow}, the field {\tt diag\_ind} is the index
of the diagonal in this row.  We require that every row have a
diagonal element (the value of this element could be zero).  The
field {\tt length} contains the number of nonzero values in this row.
The field {\tt col} is a pointer to an array of integer values that
represent the column number of each nonzero value in the row.  These
column numbers must be sorted in ascending order.  The field {\tt nz}
is a pointer to an array of double-precision values that are the
nonzero values in the row.

The mapping structure serves three purposes: (1) the mapping of
local row number to global row numbers, (2) the mapping of global
row numbers to local row numbers, and (3) the mapping of global row
number to processor number.  We provide routines for you
to set up and perform this mapping (details on these routines
are given in the ``man'' pages).  You may, however, 
set up your own mapping and use your own routines through this data
structure.  The local row numbers on every processor run from
{\tt 0} to {\tt num\_rows - 1}; the global row numbers run from {\tt 0} to
{\tt global\_num\_rows - 1}.  Each local row has a corresponding
global row number.

{\footnotesize
\begin{verbatim}
  typedef struct __BSmapping {
      void  *vlocal2global;    /* data for mapping local to global */
      void (*flocal2global)(); /* a function for mapping local to global */
      void (*free_l2g)();      /* a function for free'ing the l2g data */
      void  *vglobal2local;    /* data for mapping global to local */
      void (*fglobal2local)(); /* a function mapping global to local */
      void (*free_g2l)();      /* a function for free'ing the g2l data */
      void  *vglobal2proc;     /* data for mapping global to proc */
      void (*fglobal2proc)();  /* a function mapping global to proc */
      void (*free_g2p)();      /* a function for free'ing the g2p data */
  } BSmapping;
\end{verbatim}
}

The field {\tt vlocal2global} is a pointer to data that
is passed into the local to global mapping function (if you are
doing the mapping, you can make this point to whatever you wish).
The field {\tt flocal2global} is a pointer to a function
for performing the local to global mapping.  
The field {\tt free\_l2g} is a pointer to a function for freeing
the data in the field {\tt vlocal2global}.
The function for performing the local to global mapping 
takes five arguments.

{\footnotesize
\begin{verbatim}
  int        length;     /* the number of row numbers to translate */
  int        *req_array; /* the array of local row numbers to translate */
  int        *ans_array; /* the array of corresponding global row numbers */
  BSprocinfo *procinfo;  /* the processor information context */
  BSmapping  *map;       /* the mapping data structure */
\end{verbatim}
}

The next three fields ({\tt vglobal2local}, {\tt fglobal2local},
and {\tt free\_g2l}) are exactly the same except the mapping
is from global to local row number.
The mapping is performed only for rows that are local to
the processor; if the mapping is attempted for a nonlocal
global row number, a value of {\tt -1} is placed in the
{\tt ans\_array}.
The arguments to the mapping function are as follows.

{\footnotesize
\begin{verbatim}
  int        length;     /* the number of row numbers to translate */
  int        *req_array; /* the array of global row numbers to translate */
  int        *ans_array; /* the array of corresponding local row numbers */
  BSprocinfo *procinfo;  /* the processor information context */
  BSmapping  *map;       /* the mapping data structure */
\end{verbatim}
}

The last three fields ({\tt vglobal2proc}, {\tt fglobal2proc}, and
{\tt free\_g2p}) are exactly the same except the mapping is from
global row number to processor number.\footnote{This routine will
be called by a processor for only those global row numbers that are local
to that processor or for those global row numbers that are connected in
the sparse matrix to rows that are local to that processor.}
The arguments to the mapping function are as follows.

{\footnotesize
\begin{verbatim}
  int        length;     /* the number of row numbers to translate */
  int        *req_array; /* the array of global row numbers to translate */
  int        *ans_array; /* the array of corresponding processor numbers */
  BSprocinfo *procinfo;  /* the processor information context */
  BSmapping  *map;       /* the mapping data structure */
\end{verbatim}
}

\newpage
