paper.tex

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

%\documentstyle[12pt]{article}  
\documentclass[12pt]{article}
\usepackage{graphicx}

%% page lay-out  / RUNNING HEAD 
\pagestyle{myheadings} 
\markright{\underline{SPARSKIT \hskip 5.3in} \hskip -1.0in}
\setlength{\headheight}{0.3in} 
\setlength{\headsep}{0.3in}
%% 
\setlength{\textheight}{8.7in} 
\setlength{\textwidth}{6.2in}     
\setlength{\oddsidemargin}{0.2in}  % 
\setlength{\evensidemargin}{0.2in} % 
\setlength{\parindent}{0.2in} %
\setlength{\topmargin}{-0.3in} %%
%% abstract redefinition.
\def\@abssec#1{\vspace{.5in}\footnotesize \parindent 0.2in 
{\bf #1. }\ignorespaces}
\def\abstract{\@abssec{Abstract}}
%%
\setcounter{secnumdepth}{5}
\setcounter{tocdepth}{5}
%%  a few macros 
\def\half{{1\over2}}%
\def\del{\partial} %
\def\nref#1{(\ref{#1})} 
%% more macros: for indented boxes. 
\def\marg#1{\parbox[b]{1.3in}{\bf #1}} 
\def\disp#1{\parbox[t]{4.62in}{#1} \vskip 0.2in } 
%%
%\input{psfig}

\title{
\parbox{4in}{SPARSKIT: a basic tool kit for sparse 
matrix computations } }
\author{\parbox{4in}{VERSION 2\\Youcef Saad\thanks{
Work done partly at CSRD, university of Illinois and partly at RIACS
(NASA Ames Research Center). Current address: Computer Science Dept.,
University of Minnesota, Minneapolis, MN 55455.
This work was supported in part by the NAS Systems 
Division, via Cooperative Agreement NCC 2-387 between NASA and 
the University Space Research Association (USRA)
and in part  by the Department of Energy under grant 
DE-FG02-85ER25001.}}}

\date{ } 

\begin{document}
\bibliographystyle{plain}
%\bibliographystyle{SIAM}

\maketitle

\vskip 1.5in

\centerline{{\it June 6, 1994} } 
%\centerline{{\it May 21, 1990} } 
%\centerline{{\it Updated June 5, 1993 --- Version 2} }  

\thispagestyle{empty}

\begin{abstract} 
This paper presents the main features of a tool package for 
manipulating and working with sparse matrices.
One of the  goals of the package is to provide 
basic tools to facilitate exchange of software and data
between researchers in sparse matrix computations.
Our starting point is the Harwell/Boeing collection of matrices
for which we provide a number of tools. 
Among other things the package provides programs for converting
data structures, printing simple statistics on a matrix, 
plotting a matrix profile, performing  basic linear algebra 
operations  with sparse matrices  and so on.
\end{abstract}

\newpage

\section{Introduction} Research   on   sparse  matrix   techniques  has  become
increasingly complex, and this trend is likely to accentuate if only
because  of the growing need 
to design efficient sparse matrix algorithms for modern supercomputers.   
While there  are a  number of packages and `user
friendly' tools, for  performing computations  with small dense
matrices there is a lack of any similar tool or in fact of any 
general-purpose libraries for 
working with sparse  matrices.   Yet a  collection of  a few  basic programs to
perform some elementary and  common tasks  may be  very useful  in reducing the
typical time to implement and test sparse matrix algorithms.   That a common 
set
of routines  shared  among  researchers  does not  yet exist for sparse matrix
computation is rather surprising.  Consider the contrasting  situation in dense
matrix computations.  The Linpack  and Eispack  packages developed  in the 70's
have been of tremendous  help in  various areas  of scientific  computing.  
One might speculate on the number of hours of programming efforts 
saved worldwide thanks to the widespread availability  of these  packages.
In contrast,  it is  often the case that  researchers in  sparse  matrix 
computation  
code their own subroutine for  such  things as converting the storage mode
of a matrix or for reordering a matrix
according to a certain permutation.  One of the  reasons for this situation
might be the absence of any standard for sparse
matrix computations.  For instance, the number of different data
structures used to store sparse matrices in various applications is
staggering.  For the same basic data structure there often exist a
large number of variations in use.  As sparse matrix computation
technology is maturing there is a desperate need for some standard for
the basic storage schemes and possibly, although this is more
controversial, for the basic linear algebra operations.  

An important example where a package such as SPARSKIT can be helpful is for
exchanging matrices for research or other purposes.  In this
situation, one must often translate the matrix from some initial data
structure in which it is generated, into a different desired data
structure.  One way around this difficulty is to restrict 
the number of schemes that can be used and set  some standards.
 However, this is not
enough because often the data structures are chosen for their
efficiency and convenience, and it is not reasonable to ask
practitioners to abandon their favorite storage schemes.  What is
needed is a large set of programs to translate one data structure into
another. In the same vein, subroutines that generate test matrices
would be extremely valuable since they would allow users to have
access to a large number of matrices without the burden of actually
passing large sets of data.

A useful collection of sparse matrices known as the Harwell/Boeing
collection, which is publically available \cite{Duff-HB}, has been
widely used in recent years for testing and comparison purposes.
Because of the importance of this collection many of the tools in
SPARSKIT can be considered as companion tools to it. For
example, SPARSKIT supplies simple routines to create a Harwell/Boeing (H/B)
file from a matrix in any format, tools for creating pic files in
order to plot a H/B matrix, a few routines that will deliver
statistics for any H/B matrix, etc.. However, SPARSKIT is not limited
to being a set of tools to 
work with H/B matrices. Since one of our main motivations is
research on iterative methods, we provide numerous subroutines that may help
researchers in this specific area.  
SPARSKIT will hopefully be an evolving package
that will benefit from contributions from other researchers. This
report is a succinct description of the  package in this release.

\begin{figure}[h]
%\special{psfile=dir.eps vscale = 75 hscale = 75 hoffset =0 voffset= -30}
\includegraphics[width=15cm]{dir}
\caption {General organization of SPARSKIT.}
\label{organization}
%\vskip 0.1cm
\end{figure}

\section{Data structures for sparse matrices and the conversion routines}

One of the difficulties in sparse matrix computations is the variety
of types of matrices that are encountered in practical applications.
The purpose of each of these schemes is to gain efficiency both in
terms of memory utilization and arithmetic operations.  As a result
many different ways of storing sparse matrices have been devised to
take advantage of the structure of the matrices or the specificity of
the problem from which they arise.  For example if it is known that a
matrix consists of a few diagonals one may simply store these
diagonals as vectors and the offsets of each diagonal with respect to
the main diagonal.  If the matrix is not regularly structured, then
one of the most common storage schemes in use today is what we refer
to in SPARSKIT as the Compressed Sparse Row (CSR) scheme. In this
scheme all the nonzero entries are stored row by row  in a 
one-dimensional real array $A$ together with an array $JA$ containing
their column indices and a pointer array which contains the addresses
in $A$ and $JA$ of the beginning of each row. The order of the elements 
within each row does not matter. Also of importance
because of its simplicity is the coordinate storage scheme in which
the nonzero entries of $A$ are stored in any order together with their
row and column indices.  Many of the other existing schemes are
specialized to some extent. The reader is
referred to the book by Duff et al. \cite{Duff-book} for more details.

\subsection{Storage Formats} 	
Currently, 
the conversion routines of SPARSKIT can handle thirteen different storage
formats. These include some of the most commonly used schemes but they
are by no means exhaustive.  We found it particularly useful to have
all these storage modes when trying to extract a matrix from someone
else's application code in order, for example, to analyze it with the
tools described in the next sections or, more commonly, to try a given
solution method which requires a different data structure than the
one originally used in the application.  Often the matrix is stored in
one of these modes or a variant that is very close to it.  We hope to
add many more conversion routines as SPARSKIT evolves.

In this section we describe in detail the storage schemes that are
handled in the FORMATS module.  For convenience we have decided to
label by a three character name each format used.  We start by listing
the formats and then describe them in detail  in separate subsections
(except for the dense format which needs no detailed description).	

\begin{description}
\item{{\bf DNS}} Dense format
\item{{\bf BND}} Linpack Banded format
\item{{\bf CSR}} Compressed Sparse Row format 
\item{{\bf CSC}} Compressed Sparse Column format 
\item{{\bf COO}} Coordinate format
\item{{\bf ELL}} Ellpack-Itpack generalized diagonal format
\item{{\bf DIA}} Diagonal format
\item{{\bf BSR}} Block Sparse Row format
\item{{\bf MSR}} Modified Compressed Sparse Row format
\item{{\bf SSK}} Symmetric Skyline format
\item{{\bf NSK}} Nonsymmetric Skyline format
\item{{\bf LNK}} Linked list storage format 
\item{{\bf JAD}} The Jagged Diagonal format 
\item{{\bf SSS}} The Symmetric Sparse Skyline format
\item{{\bf USS}} The Unsymmetric Sparse Skyline format
\item{{\bf VBR}} Variable Block Row format
\end{description}

In the following sections we denote by $A$ the matrix under
consideration and by $N$ its row dimension and $NNZ$ the number of its
nonzero elements.

\subsubsection{Compressed Sparse Row and related formats
 (CSR, CSC and MSR)} The Compressed Sparse Row format is the basic
format used in SPARSKIT. Its  data structure consists of three arrays.

\begin{itemize} 

\item A real array $A$ containing the real values $a_{ij}$ stored row by row,
from row 1 to $N$. The length of $A$ is NNZ.

\item An integer array $JA$ containing the column indices
of the elements $a_{ij}$ as stored in the array $A$.  The length of
$JA$ is NNZ.

\item An integer array $IA$ containing the pointers to the
beginning of each row in the arrays $A$ and $JA$. Thus the content of
$IA(i)$ is the position in arrays $A$ and $JA$ where the $i$-th row
starts.  The length of $IA$ is $N+1$ with $IA(N+1)$ containing the
number $IA(1)+NNZ$, i.e., the address in $A$ and $JA$ of the beginning
of a fictitious row $N+1$.

\end{itemize}
The order of the nonzero elements within the same row are not important. 
A variation to this scheme is to sort the elements in each row 
in such a way that their column positions are in increasing order.
When this sorting in enforced, it is often possible to 
make substantial savings in the number of operations of 
some well-known algorithms. 
The Compressed Sparse Column format is identical with the Compressed
Sparse Row format except that the columns of $A$ are stored instead of
the rows. In other words the Compressed Sparse Column format is simply
the Compressed Sparse Row format for the matrix $A^T$.

The Modified Sparse Row (MSR) format is a rather common variation of
the Compressed Sparse Row format which consists of keeping the main
diagonal of $A$ separately. The corresponding data structure consists
of a real array $A$ and an integer array $JA$. The first $N$ positions
in $A$ contain the diagonal elements of the matrix, in order.  The position
$N+1$ of the array $A$ is not used. Starting from position $N+2$, the
nonzero elements of $A$, excluding its diagonal elements, are stored
row-wise. Corresponding to each element $A(k)$ the integer $JA(k)$ is
the column index of the element $A(k)$ in the matrix $A$. The $N+1$
first positions of $JA$ contain the pointer to the beginning of each
row in $A$ and $JA$. The advantage of this storage mode is that many
matrices have a full main diagonal, i.e., $a_{ii} \ne 0, i=1,\ldots,
N$, and this diagonal is best represented by an array of length $N$.
This storage mode is particularly useful for triangular matrices with
non-unit diagonals. Often the diagonal is then stored in inverted form