paper.tex

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

\marg{ VBRMV }\disp{ Sparse matrix - full vector product in VBR format.} 

\marg{ LSOL } 
\disp{  Unit lower triangular system solution. Matrix stored in
Compressed Sparse Row (CSR) format. }

\marg{ LDSOL  }\disp{Lower triangular system solution. Matrix stored in
Modified Sparse Row (MSR) format. Diagonal elements inverted. }

\marg{ LSOLC  }\disp{ 
Unit lower triangular system solution. Matrix stored in
 Compressed Sparse Column (CSC) format.   }

\marg{ LDSOLC }\disp{  
Lower triangular system solution. Matrix stored in
Modified Sparse Column (MSC) format with diagonal elements inverted. }

\marg{ LDSOLL }\disp{ 
Unit lower triangular system solution with the level scheduling
approach.  Matrix 
stored in Modified Sparse Row format, with diagonal elements inverted.}

\marg{ USOL }\disp{  Unit upper triangular system solution. 
Matrix stored in Compressed Sparse Row (CSR) format. }

\marg{ UDSOL  }\disp{  Upper triangular system solution. 
Matrix stored in Modified Sparse Row (MSR) format. Diagonal 
elements inverted. }

\marg{ USOLC  }\disp{ 
Unit upper triangular system solution. Matrix stored in
Compressed Sparse Column (CSC) format.   } 

\marg{ UDSOLC }\disp{  
Upper triangular system solution. Matrix stored in
Modified Sparse Column (MSC) format with diagonal elements inverted. }

\vskip 0.3in
Most of the above routines are  short and rather straightforward.
A long test program  is provided to run all of the subroutines
on a large number of matrices that are dynamically generated
using the MATGEN module. 

\section{The basic statistics and information routines}
It is sometimes very  informative when analyzing
solution methods, to be able in a short amount of time to 
obtain some statistical information about a sparse matrix.
The purpose of the subroutine info1, is to print out such
information. The first question we had to address 
was to determine the type of information that
is inexpensive to obtain and yet practical and useful.
The simplest and most common statistics
are: total number of nonzero elements, average number of nonzero
elements per row (with standard deviation), band size.
Our preliminary package Info1 contains the above and a 
number of other features. For example it answers the following
questions: Is the matrix lower triangular, upper triangular?
does it have a symmetric structure? If not how close is it 
from having this property? Is it weakly row-diagonally dominant?
What percentage of the rows are weakly diagonally dominant?
Same questions for column diagonal dominance.
A sample output from  info1 is listed in 
Figure\ref{Fig1}. This print-out was  generated by typing 
\begin{center}
{\tt info1.ex < pores\_2}
\end{center}
%\[ {\rm info1.ex}  < {\rm pores\_2} \]
where {\tt pores\_2} is a file containing a matrix in H/B format.

If the Harwell-Boeing matrix is symmetric then Info1 takes this
information into account to obtain the correct information
instead of the information on  the lower triangular part only.
Moreover, in cases where only the pattern is provided (no real
values), then info1 will print a message to this effect and 
will then give information related only to the structure of 
the matrix. The output for an example of this type is shown in 
Figure~\ref{Fig2}. We should point out that the runs for these
two tests were basically instantaneous on a Sun-4 workstation.

Currently, this module contains the following subroutines:

\vskip 0.3in
 
\marg{ N\_IMP\_DIAG }\disp{ Computes the most important diagonals.}

\marg{ DIAG\_DOMI }\disp{ Computes the percentage of weakly diagonally 
dominant rows/columns.}

\marg{ BANDWIDTH }\disp{ Computes the lower, upper, maximum, and 
average bandwidths.}

\marg{ NONZ }\disp{ Computes maximum numbers of nonzero elements
per column/row, min numbers of nonzero elements per column/row,
and numbers of zero columns/rows.}

\marg{ FROBNORM }\disp{ Computes the Frobenius norm of A.}

\marg{ ANSYM }\disp{ Computes the Frobenius norm of the symmetric and
non-symmetric parts of A, computes the number of matching elements in symmetry 
and the relative symmetry match.
The routine ANSYM provides some information on the degree of symmetry of A.}

\marg{ DISTAIJ }\disp{ Computes the average distance of a(i,j) from diag and
standard deviation  for this average.}

\marg{ SKYLINE }\disp{ Computes the number of nonzeros in the skyline storage.}

\marg{ DISTDIAG }\disp{ Computes the numbers of elements in each diagonal.}

\marg{ BANDPART }\disp{ Computes the bandwidth of the banded matrix,
which contains 'nper' percent of the original matrix.}


\marg{ NONZ\_LUD }\disp{ Computes the number of nonzero elements in strict
lower part, strict upper part, and main diagonal.}

\marg{ AVNZ\_COL }\disp{ Computes average number of nonzero elements/column
and standard deviation for the average.}

\marg{ VBRINFO }\disp{ Prints information about matrices in variable block row 
format.}

% This has been updated to match the new code. -- June 3, 1994.
%* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
%* unsymmetric matrix from pores                                           *
%*                    Key = pores_2  , Type = rua                          *
%* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
%    *  Dimension N                                      =       1224  *
%    *  Number of nonzero elements                       =       9613  *
%    *  Average number of nonzero elements/Column        =     7.8538  *
%    *  Standard deviation for above average             =     5.4337  *
%    *  Nonzero elements in strict upper part            =       4384  *
%    *  Nonzero elements in strict lower part            =       4005  *
%    *  Nonzero elements in main diagonal                =       1224  *
%    *  Weight of longest column                         =         30  *
%    *  Weight of shortest column                        =          2  *
%    *  Weight of longest row                            =         30  *
%    *  Weight of shortest row                           =          2  *
%    *  Matching elements in symmetry                    =       6358  *
%    *  Relative Symmetry Match (symmetry=1)             =     0.6614  *
%    *  Average distance of a(i,j)  from diag.           =  0.615E+02  *
%    *  Standard deviation for above average             =  0.103E+03  *
%    *-----------------------------------------------------------------*
%    *  Frobenius norm of A                              =  0.150E+09  *
%    *  Frobenius norm of symmetric part                 =  0.100E+09  *
%    *  Frobenius norm of nonsymmetric part              =  0.951E+08  *
%    *  Maximum element in A                             =  0.378E+08  *
%    *  Percentage of weakly diagonally dominant rows    =  0.481E+00  *
%    *  Percentage of weakly diagonally dominant columns =  0.490E-02  *
%    *-----------------------------------------------------------------*
%    *  Lower bandwidth  (max: i-j, a(i,j) .ne. 0)       =        470  *
%    *  Upper bandwidth  (max: j-i, a(i,j) .ne. 0)       =        471  *
%    *  Maximum Bandwidth                                =        736  *
%    *  Average Bandwidth                                =  0.190E+03  *
%    *  Number of nonzeros in skyline storage            =     340385  *
%    *  90% of matrix is in the band of width            =        527  *
%    *  80% of matrix is in the band of width            =        145  *
%    *  The total number of nonvoid diagonals is         =        367  *
%    *  The 10 most important diagonals are (offsets)    :             *
%    *     0     1    -1    -2     2    -3   -32  -264   264    32     *
%    *  The accumulated percentages they represent are   :             *   
%    *  12.7  24.6  31.7  37.9  43.6  49.0  52.4  55.7  58.6  61.4     *
%    *-----------------------------------------------------------------*
%    *  The matrix does not have a block structure                     *
%    *-----------------------------------------------------------------*
\begin{figure}
\begin{verbatim}
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* UNSYMMETRIC MATRIX FROM PORES                                           *
*                    Key = PORES 2  , Type = RUA                          *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
    *  Dimension N                                      =       1224  *
    *  Number of nonzero elements                       =       9613  *
    *  Average number of nonzero elements/Column        =     7.8538  *
    *  Standard deviation for above average             =     5.4337  *
    *  Nonzero elements in strict lower part            =       4384  *
    *  Nonzero elements in strict upper part            =       4005  *
    *  Nonzero elements in main diagonal                =       1224  *
    *  Weight of longest column                         =         30  *
    *  Weight of shortest column                        =          2  *
    *  Weight of longest row                            =         16  *
    *  Weight of shortest row                           =          5  *
    *  Matching elements in symmetry                    =       6358  *
    *  Relative Symmetry Match (symmetry=1)             =     0.6614  *
    *  Average distance of a(i,j)  from diag.           =  0.615E+02  *
    *  Standard deviation for above average             =  0.103E+03  *
    *-----------------------------------------------------------------*
    *  Frobenius norm of A                              =  0.150E+09  *
    *  Frobenius norm of symmetric part                 =  0.103E+09  *
    *  Frobenius norm of nonsymmetric part              =  0.980E+08  *
    *  Maximum element in A                             =  0.378E+08  *
    *  Percentage of weakly diagonally dominant rows    =  0.490E-02  *
    *  Percentage of weakly diagonally dominant columns =  0.481E+00  *
    *-----------------------------------------------------------------*
    *  Lower bandwidth  (max: i-j, a(i,j) .ne. 0)       =        470  *
    *  Upper bandwidth  (max: j-i, a(i,j) .ne. 0)       =        471  *
    *  Maximum Bandwidth                                =        736  *
    *  Average Bandwidth                                =  0.190E+03  *
    *  Number of nonzeros in skyline storage            =     342833  *
    *  90% of matrix is in the band of width            =        527  *
    *  80% of matrix is in the band of width            =        145  *
    *  The total number of nonvoid diagonals is         =        367  *
    *  The 10 most important diagonals are (offsets)    :             *
    *     0    -1     1     2    -2     3    32   264  -264   -32     *
    *  The accumulated percentages they represent are   :             *
    *  12.7  24.6  31.7  37.9  43.6  49.0  52.4  55.7  58.6  61.4     *
    *-----------------------------------------------------------------*
    *  The matrix does not have a block structure                     *
    *-----------------------------------------------------------------*
\end{verbatim}
\caption{Sample output from Info1.ex \label{Fig1} } 
\end{figure}


%* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
%* SYMMETRIC PATTERN FROM CANNES,LUCIEN MARRO,JUNE 1981.                   *
%*                    Key = CAN 1072 , Type = PSA                          *
%* No values provided - Information on pattern only                        *
%* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
%    *  Dimension N                                      =       1072  *
%    *  Number of nonzero elements                       =       6758  *
%    *  Average number of nonzero elements/Column        =    11.6082  *
%    *  Standard deviation for above average             =     5.6474  *
%    *  Nonzero elements in strict upper part            =       5686  *
%    *  Nonzero elements in strict lower part            =       5686  *
%    *  Nonzero elements in main diagonal                =       1072  *
%    *  Weight of longest column                         =         35  *
%    *  Weight of shortest column                        =          6  *
%    *  Matching elements in symmetry                    =       6758  *
%    *  Relative Symmetry Match (symmetry=1)             =     1.0000  *
%    *  Average distance of a(i,j)  from diag.           =  0.110E+03  *
%    *  Standard deviation for above average             =  0.174E+03  *
%    *-----------------------------------------------------------------*
%    *  Lower bandwidth  (max: i-j, a(i,j) .ne. 0)       =       1048  *
%    *  Upper bandwidth  (max: j-i, a(i,j) .ne. 0)       =       1048  *
%    *  Maximum Bandwidth                                =       1055  *
%    *  Average Bandwidth                                =  0.376E+03  *
%    *  Number of nonzeros in skyline storage            =     277248  *
%    *  90% of matrix is in the band of width            =        639  *
%    *  80% of matrix is in the band of width            =        343  *
%    *  The total number of nonvoid diagonals is         =        627  *
%    *  The  5 most important diagonals are (offsets)    :             *
%    *     0    -1    -2    -3    -4                                   *
%    *  The accumulated percentages they represent are   :             *
%    *  15.9  24.7  29.7  33.9  36.3                                   *
%    *-----------------------------------------------------------------*
%    *  The matrix does not have a block structure                     *
%    *-----------------------------------------------------------------*
\begin{figure}
\begin{verbatim}
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* SYMMETRIC PATTERN FROM CANNES,LUCIEN MARRO,JUNE 1981.                   *
*                    Key = CAN 1072 , Type = PSA                          *
* No values provided - Information on pattern only                        *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
    *  Dimension N                                      =       1072  *
    *  Number of nonzero elements                       =       6758  *
    *  Average number of nonzero elements/Column        =     6.3041  *
    *  Standard deviation for above average             =     6.2777  *
    *  Nonzero elements in s