paper.tex

这是Yousef Saad编写的矩阵运算的Fortran软件包（A basic tool-kit for sparse matrix computations (Version 2),包含常见的排序

\marg{ INFDIA  }\disp{ Computes the number of nonzero elements 
of each of the $2n-1$ diagonals of a matrix. Note that the first diagonal 
is the diagonal with offset $-n$ which consists of the entry
$a_{n,1}$ and the last one is the diagonal with offset $n$ which consists
of the element $a_{1,n}$.}

\marg{ AMUBDG }\disp{ Computes the number of nonzero elements
in each row of the product of two sparse matrices $A$ and $B$.
Also returns the total number of nonzero elements.}

\marg{ APLBDG }\disp{ Computes the number of nonzero elements
in each row of the sum of two sparse matrices $A$ and $B$.
Also returns the total number of nonzero elements.}

\marg{ RNRMS }\disp{ Computes the norms of the rows of a matrix.
The usual three norms $\|.\|_1, \|.\|_2, $ and $\|.\|_{\infty} $
are supported. }

\marg{ CNRMS }\disp{ Computes the norms of the columns of a matrix.
Similar to RNRMS. }

\marg{ ROSCAL }\disp{ Scales the rows of a matrix by their norms. 
The same three norms as in RNRMS are available.  }

\marg{ COSCAL }\disp{ Scales the columns of a matrix by their norms.
The same three norms as in RNRMS are available. }

\marg{ADDBLK}\disp{Adds a matrix B into a block of A. }

\marg{GET1UP}\disp{Collects the first elements of each row of the upper
triangular portion of the matrix. }
 
\marg{XTROWS}\disp{Extracts given rows from a matrix in CSR format.}

\marg{CSRKVSTR}\disp{Finds block partitioning of matrix in CSR format.}

\marg{CSRKVSTC}\disp{Finds block column partitioning of matrix in CSR format.}

\marg{KVSTMERGE}\disp{Merges block partitionings for conformal row/column pattern.}


\section{Input/Output routines}
The INOUT module of SPARSKIT  comprises a few routines for reading,
writing, and for plotting and visualizing the structure 
of sparse matrices. Many of these routines  are essentially geared towards 
the utilization of the Harwell/Boeing collection of matrices.
There are currently eleven subroutines in this module.

\vskip .5in

\marg{ READMT}\disp{ Reads a matrix in the Harwell/Boeing format.} 

\marg{ PRTMT}\disp{ Creates a Harwell Boeing file from an arbitrary
 matrix in CSR or CSC format.} 

\marg{ DUMP }\disp{DUMP prints the rows of a 
 matrix in a file, in a nice readable format.
The best format is internally calculated depending on the number of
nonzero elements. This is a simple routine which might be 
helpful for debugging purposes.}  

\marg{ PSPLTM }\disp{Generates a post-script plot of the non-zero 
pattern of A.}

\marg{ PLTMT }\disp{Creates a pic file for plotting the pattern of a 
matrix.} 

\marg{ SMMS }\disp{Write the matrx in a format used in SMMS package.}

\marg{ READSM }\disp{Reads matrices in coordinate format (as in SMMS 
package).}

\marg{ READSK }\disp{Reads matrices in CSR format (simplified H/B format).}

\marg{ SKIT }\disp{Writes matrices to a file, format same as above.}

\marg{ PRTUNF }\disp{Writes matrices (in CSR format) in unformatted files.}

\marg{ READUNF }\disp{Reads unformatted file containing matrices in CSR format.}

 
\vskip 0.3in

The routines readmt and prtmt allow to read and create files
containing matrices stored in the H/B format. 
For details concerning this format the reader is referred to
\cite{Duff-HB} or the summary given in the documentation  of
the subroutine READMT. While the purpose of
readmt is clear, it is not obvious that one single 
subroutine can write a matrix in H/B format and still satisfy
the needs of all users. For example for some matrices all nonzero
entries are actually integers and a format using say a 10 digit
mantissa may entail an enormous waste of storage if the matrix
is large. The solution provided is to compute internally the best
formats for the integer arrays IA and JA. A little help is 
required from the user for the real values in the arrays A and
RHS. Specifically, the desired format is obtained from
a parameter of the subroutine by using a simple notation, 
which is explained in detail in the documentation of the routine. 

Besides the pair of routines that can read/write matrices in H/B
format, there are three other pairs which can be used to input and
output matrices in different formats. The SMMS and READSM pair write
and read matrices in the format used in the package SMMS.
Specifically, READSM reads a matrix in SMMS format from a file and outputs
it in CSR format. SMMS accepts a matrix in CSR format and
writes it to a file in SMMS format. The SMMS format is
essentially a COO format. 
The size of the matrix appears in the first line of the file. Each other
line of the file
contains triplets in the form of ($i$, $j$, $a_{ij}$) which
denote the non-zero elements of the matrix.
Similarly, READSK and SKIT read and write matrices in CSR format. 
This pair is very similar to READMT and PRTMT, only that the
files read/written by READSK and SKIT do not have headers. The pair 
READUNF and PRTUNF reads and writes the matrices (stored as $ia$, $ja$
and $a$) in binary form,
i.e.~the number in the file written by PRTUNF will be in machine
representations. The primary motivation for this is that
handling the arrays in binary form takes less space than in the
usual ASCII form, and is usually  faster.
If the matrices are large and they are only used on compatible computers,
it might be desirable to use unformatted files.

We found it extremely useful to be able to visualize a sparse matrix,
notably for debugging purposes.  A simple look at the plot can
sometimes reveal whether the matrix obtained from some reordering
technique does indeed have the expected structure.  For now two simple
plotting mechanisms are provided. First, a preprocessor called PLTMT
to the Unix utility `Pic'  allows one to generate a pic file from a
matrix that is in the Harwell/Boeing format or any other format. For
example for a Harwell/Boeing matrix file, the command is of the form
%%\[hb2pic.ex \; < \; HBfilename \] 
\begin{center}
{\tt hb2pic.ex < HB\_file.}
\end{center}
The output file is then printed by the usual troff or TeX commands. A
translation of this routine into one that generates a post-script file
is also available (called PSPLTM). We should point out that the
plotting routines are very simple in nature and should not be used to
plot large matrices. For example the pltmt routine outputs one pic
command line for every nonzero element.  This constitutes a convenient
tool for document preparation for example.  Matrices of size just up
to a few thousands can be printed this way.  Several options
concerning the size of the plot and caption generation are available.

There is also a simple utility program called ``hb2ps'' which takes a
matrix file with HB format and translates it into a post-script file.
The usage of this program is as follows:
\begin{center}
{\tt hb2ps.ex < HB\_file > Postscript\_file.}
\end{center}
%%\[ hb2ps.ex   < HB\_file > Postscript\_file. \]
The file can be previewed with ghostscript.
The following graph shows a pattern of an unsymmetric matrix.

\begin{figure}[htb]
%\centerline{\psfig{figure=jpwh.ps,width=5in}}
\includegraphics[width=5in]{jpwh}
%\vskip 5.5in
%\special{psfile=jpwh.ps vscale = 100 hscale = 100 hoffset = -85 voffset= -450}
%\special{psfile=jpwh.ps hoffset = -85}
\end{figure}

\section{Basic algebraic operations}
The usual algebraic operations involving two matrices,
such as $C= A+ B$, $C= A+\beta B$, $C= A B $, etc..,
are fairly common in sparse matrix computations.
These basic matrix operations
are included in the module called BLASSM.  In addition there is a
large number of basic operations, involving a sparse matrix
and a vector, such as matrix-vector products and
triangular system solutions that are very commonly used. Some of
these are included in the module MATVEC.
Sometimes it is desirable to compute the 
patterns of the matrices $A+B$ and $AB$, or in fact of any result 
of the basic algebraic  operations. This can be implemented by
way of job options which will determine whether to fill-in the real
values or not during the computation.  
We now briefly describe the contents of each of the 
two modules BLASSM and MATVEC. 

\subsection{The BLASSM module} 
Currently, the module BLASSM (Basic Linear Algebra Subroutines for
Sparse Matrices) contains the following nine subroutines:

\vskip 0.3in

\marg{ AMUB }\disp{ Performs the product of two matrices, i.e.,
computes $C = A B $, where $A$ and $B$ are both in CSR format.}

\marg{  APLB }\disp{ Performs the addition of two matrices, i.e.,
computes $C = A + B $, where $A$ and $B$ are both in CSR format.}

\marg{ APLSB }\disp{ Performs the operation $ C=A + \sigma B $, 
where $\sigma$ is a scalar, and $A, B$ are two matrices in 
CSR format. }

\marg{ APMBT }\disp{ Performs either the addition $C = A + B^T$ or the 
subtraction $C=A-B^T$.  }

\marg{ APLSBT }\disp{ Performs the operation $C = A + s B^T$. }

\marg{ DIAMUA }\disp{   Computes the product of diagonal 
matrix (from the left) by a sparse matrix, i.e.,
computes $C = D A$, where $D$ is a diagonal matrix and $A$
is a general sparse matrix stored in CSR format. }

\marg{ AMUDIA }\disp{ Computes the product of a sparse 
matrix by a diagonal matrix from the right, i.e., 
computes $C = A D $, where $D$ is a diagonal matrix and $A$
is a general sparse matrix stored in CSR format. }

\marg{ APLDIA }\disp{   Computes the sum of a sparse matrix and a 
diagonal matrix, $ C = A + D $.  }

\marg{ APLSCA }\disp{Performs an in-place
addition of a scalar to the diagonal entries of 
a sparse matrix, i.e., performs the operation
 $A := A + \sigma I$.} 

\vskip 0.3in 

Missing from this list are the routines {\bf AMUBT} which multiplies $A$ by 
the transpose of $B$, $C= AB^T$, and {\bf ATMUB } which multiplies the 
transpose of $A$ by $B$,	$C= A^T B $.

\vskip 0.3in

These are very difficult to implement and we found it better to 
perform it with two passes.
Operations of the form $ t A + s B $ have been
avoided as their occurrence does not warrant additional subroutines.
Several other operations similar to those defined for
vectors have not been included. For example the scaling
of a matrix  in sparse format is simply a scaling of its
real array $A$, which can be done with the usual BLAS1
scaling routine, on the array $A$. 


\subsection{The MATVEC module}
In its current status, this module contains matrix
by vector products and various sparse triangular 
solution methods. The contents are as follows.

\vskip 0.3in

\marg{ AMUX   }\disp{ Performs the product of a  matrix by a vector.
 Matrix stored in  Compressed Sparse Row (CSR) format.}

\marg{  ATMUX  }\disp{  Performs the product of the transpose of
a  matrix by a vector. Matrix $A$ stored in Compressed 
Sparse Row format. Can also be
viewed as the product of a matrix in the Compressed Sparse Column
format by a vector.} 

\marg{  AMUXE  }\disp{  Performs the product of a  matrix by a vector.
Matrix stored in  Ellpack/Itpack (ELL) format.}

\marg{ AMUXD  }\disp{  Performs the product of a  matrix by a vector.
Matrix stored in  Diagonal (DIA) format.}

\marg{ AMUXJ  }\disp{  Performs the product of a  matrix by a vector.
Matrix stored in  Jagged Diagonal (JAD) format.}