\chapter{SPARSE: Sparse Matrices}
\label{SPARSE MATRICES}
\typeout{{SPARSE: Sparse Matrices}}

{\footnotesize
\begin{center}
Stephen Scowcroft \\
Konrad-Zuse-Zentrum f\"ur Informationstechnik Berlin \\
Takustra\"se 7 \\
D-14195 Berlin-Dahlem, Germany \\
\end{center}
}
\ttindex{SPARSE, Sparse matrices}
\ttindex{MATRIX, see also SPARSE}

\section{Introduction}

This package extends the available matrix feature to enable 
calculations with sparse matrices. It also provides
a selection of functions that are useful in the world of linear
algebra with respect to sparse matrices. \\
The package is loaded by: {\tt load\_package sparse;}


\section{Sparse Matrix Calculations}

To extend the syntax of this class of calculations an expression type 
{\tt sparse \ttindex{SPARSE}} is added. An identifier may be declared a
sparse variable by the declaration {\tt sparse}. The size of the
sparse matrix must be declared explicitly in the matrix declaration.
This declaration \f{SPARSE} is similar to the declaration \f{MATRIX}.
Once a matrix has been declared a sparse matrix all elements of the
matrix are treated as if they were initialized to 0. When printing out 
a sparse matrix only the non-zero elements are printed due to the fact 
that only the non-zero elements of the matrix are stored. To assign values 
to the elements of the declared sparse matrix we use the same syntax as for 
matrices.

\begin{verbatim}
sparse aa(10,1),bb(200,200);
aa(1,1):=10;
bb(100,150):=a;
\end{verbatim}


\section{Linear Algebra Package for Sparse Matrices}

Most of the functions of this package are related to the functions
of the linear algebra package \f{LINALG}. For further explanation and
examples of the various functions please refer to the \f{LINALG}
package.

\subsection{Basic matrix handling}


{\small\begin{tabular}{l l l l}
spadd\_columns     \ttindex{SPADD\_COLUMNS}     & 
spadd\_rows        \ttindex{SPADD\_ROWS}        &
spadd\_to\_columns \ttindex{SPADD\_TO\_COLUMNS} &
spadd\_to\_rows    \ttindex{SPADD\_TO\_ROWS}    \\
spaugment\_columns \ttindex{SPAUGMENT\_COLUMNS} &
spchar\_poly       \ttindex{SPCHAR\_POLY}       &
spcol\_dim         \ttindex{SPCOL\_DIM}         &
spcopy\_into       \ttindex{SPCOPY\_INTO}       \\
spdiagonal         \ttindex{SPDIAGONAL}         & 
spextend           \ttindex{SPEXTEND}           &
spfind\_companion  \ttindex{SPFIND\_COMPANION}  & 
spget\_columns     \ttindex{SPGET\_COLUMNS}     \\
spget\_rows        \ttindex{SPGET\_ROWS}        & 
sphermitian\_tp    \ttindex{SPHERMITIAN\_TP}    &
spmatrix\_augment  \ttindex{SPMATRIX\_AUGMENT}  & 
spmatrix\_stack    \ttindex{SPMATRIX\_STACK}    \\
spminor            \ttindex{SPMINOR}            & 
spmult\_columns    \ttindex{SPMULT\_COLUMNS}    & 
spmult\_rows       \ttindex{SPMULT\_ROWS}       & 
sppivot            \ttindex{SPPIVOT}            \\
spremove\_columns  \ttindex{SPREMOVE\_COLUMNS}  & 
spremove\_rows     \ttindex{SPREMOVE\_ROWS}     &
sprow\_dim         \ttindex{SPROW\_DIM}         & 
sprows\_pivot      \ttindex{SPROWS\_PIVOT}      \\
spstack\_rows      \ttindex{SPSTACK\_ROWS}      & 
spsub\_matrix      \ttindex{SPSUB\_MATRIX}      &
spswap\_columns    \ttindex{SPSWAP\_COLUMNS}    & 
spswap\_entries    \ttindex{SPSWAP\_ENTRIES}    \\
spswap\_rows       \ttindex{SPSWAP\_ROWS}        
\end{tabular}}

  

\subsection{Constructors}

Functions that create sparse matrices.


\begin{tabular}{l l l l}
spband\_matrix     \ttindex{SPBAND\_MATRIX}    & 
spblock\_matrix    \ttindex{SPBLOCK\_MATRIX}   &
spchar\_matrix     \ttindex{SPCHAR\_MATRIX}    &
spcoeff\_matrix    \ttindex{SPCOEFF\_MATRIX}   \\ 
spcompanion        \ttindex{SPCOMPANION}       & 
sphessian          \ttindex{SPHESSIAN}         &
spjacobian         \ttindex{SPJACOBIAN}        & 
spjordan\_block    \ttindex{SPJORDAN\_BLOCK}   \\ 
spmake\_identity   \ttindex{SPMAKE\_IDENTITY}  
\end{tabular}


\subsection{High level algorithms}


\begin{tabular}{l l l l}
spchar\_poly       \ttindex{SPCHAR\_POLY}      & 
spcholesky         \ttindex{SPCHOLESKY}        & 
spgram\_schmidt    \ttindex{SPGRAM\_SCHMIDT}   & 
splu\_decom        \ttindex{SPLU\_DECOM}       \\
sppseudo\_inverse  \ttindex{SPPSEUDO\_INVERSE} & 
svd                \ttindex{SVD}
\end{tabular}


\subsection{Predicates}


\begin{tabular}{l l l l}
matrixp     \ttindex{MATRIXP}    & 
sparsematp  \ttindex{SPARSEMATP} &
squarep     \ttindex{SQUAREP}    & 
symmetricp  \ttindex{SYMMETRICP}  
\end{tabular}

