SPARSEKIT
Sparse Matrix Utility Package

SPARSEKIT is a FORTRAN77 library which carries out a number of operations on sparse matrices, particularly conversion between various sparse formats.

SPARSEKIT can manipulate sparse matrices in a variety of formats, and can convert from one to another. For example, a matrix can be converted from the generalized diagonal format used by ELLPACK and ITPACK to the format used by the Harwell-Boeing Sparse Matrix Collection or into LINPACK banded format.

Utilities available include converting data structures, printing simple statistics on a matrix, plotting a matrix profile, performing basic linear algebra operations (similar to the BLAS for dense matrix), and so on.

Matrix formats that are recognized include:

• BND, the LINPACK format for general banded matrices.
• BSR, block row sparse format.
• COO, coordinate format.
• CSC, compressed sparse column format.
• CSR, compressed sparse row format.
• DIA, the diagonal sparse matrix format (NOT a diagonal matrix!).
• DIAG, a diagonal matrix, stored as a vector.
• DNS, dense storage, also called full storage.
• ELL, ELLPACK/ITPACK, the format used by ELLPACK and ITPACK.
• HB, Harwell-Boeing format. (Actually, CSR format plus auxilliary data)
• JAD, the jagged diagonal format.
• LNK, linked storage format.
• MSC, modified sparse column format.
• MSR, modified sparse row format.
• SSK, Symmetric skyline format.
• SSR, Symmetric sparse row format.

Languages:

SPARSEKIT is available in a FORTRAN77 version and a FORTRAN90 version.

Related Data and Programs:

CSPARSE, a C library which carries out the direct solution of sparse linear systems.

DLAP, a FORTRAN90 library which solves sparse linear systems.

HB_IO, a FORTRAN90 library which reads and writes sparse linear systems stored in the Harwell-Boeing Sparse Matrix format.

HB_TO_ST, a FORTRAN77 program which converts the sparse matrix information stored in a Harwell-Boeing file into a sparse triplet file.

MGMRES, a FORTRAN77 library which applies the restarted GMRES algorithm to solve a sparse linear system.

MM_IO, a FORTRAN90 library which reads and writes sparse linear systems stored in the Matrix Market format.

SPARSE_CC, a data directory which contains a description and examples of the CC format, ("compressed column") for storing a sparse matrix, including a way to write the matrix as a set of three files.

SPARSE_CR, a data directory which contains a description and examples of the CR format, ("compressed row") for storing a sparse matrix, including a way to write the matrix as a set of three files.

SPARSEKIT2, a FORTRAN77 library which implements operations on sparse matrices, including conversion between various formats; this is version 2 of the library, by Yousef Saad.

SPARSEPAK, a FORTRAN90 library which reorders and solves sparse linear systems.

UMFPACK, a FORTRAN77 library which solves unsymmetric sparse linear systems, by Timothy Davis, Iain Duff.

Reference:

1. Efstratios Gallopoulos, Youcef Saad,
   Efficient solution of parabolic equations by Krylov approximation methods,
   RIACS Technical Report, 90-14.
2. Noborou Kikuchi,
   Finite element methods in mechanics,
   Cambridge University Press, 1986.
3. David Kincaid, Thomas Oppe, John Respess, David Young,
   ITPACKV 2C User's Guide,
   Technical Report CNA-191.
   Center for Numerical Analysis,
   University of Texas at Austin, 1984.
4. Donald Knuth,
   The Art of Computer Programming,
   Volume 3: Sorting and Searching,
   Addison-Wesley, 1973.
5. Ole Osterby, Zahari Zlatev,
   Direct Methods for Sparse Matrices,
   Springer-Verlag 1983.
6. Youcef Saad,
   Sparsekit: a basic tool kit for sparse matrix computations,
   Technical Report, Computer Science Department,
   University of Minnesota, June 1994.
7. Youcef Saad,
   Analysis of some Krylov subspace approximations to the matrix exponential operator,
   RIACS Technical Report, 90-14.
8. Yousef Saad,
   Iterative Methods for Sparse Linear Systems,
   Second Edition,
   SIAM, 2003,
   ISBN: 0898715342.
9. Zahari Zlatev, Kjeld Schaumburg, Jerzy Wasniewski,
   A testing Scheme for Subroutines Solving Large Linear Problems,
   Computers and Chemistry,
   Volume 5, Number 2-3, pages 91-100, 1981.

Source Code:

• sparsekit.f, the source code.
• sparsekit.sh, commands to compile the source code.

Examples and Tests:

Sample problem 1:

• sparsekit_prb01.f, a sample calling program.
• sparsekit_prb01.sh, commands to compile and run the sample program.
• sparsekit_prb01_output.txt, the output file.

Sample problem 2:

• sparsekit_prb02.f, a sample calling program.
• sparsekit_prb02.sh, commands to compile and run the sample program.
• sparsekit_prb02_output.txt, the output file.

Sample problem 3:

• sparsekit_prb03.f, a sample calling program.
• sparsekit_prb03.sh, commands to compile and run the sample program.
• sparsekit_prb03_output.txt, the output file.

Sample problem 4 takes a banded matrix of order 16, stored as a dense matrix, converts it to CSR format and sorted CSR format.

• sparsekit_prb04.f, a sample calling program.
• sparsekit_prb04.sh, commands to compile and run the sample program.
• sparsekit_prb04_output.txt, the output file.

Sample problem 5:

• sparsekit_prb05.f, a sample calling program.
• sparsekit_prb05.sh, commands to compile and run the sample program.
• sparsekit_prb05_output.txt, the output file.

Sample problem 6:

• sparsekit_prb06.f, a sample calling program.
• sparsekit_prb06.sh, commands to compile and run the sample program.
• sparsekit_prb06_output.txt, the output file.

Sample problem 7:

• sparsekit_prb07.f, a sample calling program.
• sparsekit_prb07.sh, commands to compile and run the sample program.
• sparsekit_prb07_output.txt, the output file.

Sample problem 8 generates three sample matrices from the Zlatev set, and writes them to Harwell-Boeing format files:

• sparsekit_prb08.f, a sample calling program.
• sparsekit_prb08.sh, commands to compile and run the sample program.
• sparsekit_prb08_output.txt, the output ffile.
• zlatev1_hb.txt, Zlatev sample matrix 1.
• zlatev2_hb.txt, Zlatev sample matrix 2.
• zlatev3_hb.txt, Zlatev sample matrix 3.

Sample problem 9:

• sparsekit_prb09.f, a sample calling program.
• sparsekit_prb09.sh, commands to compile and run the sample program.
• sparsekit_prb09_output.txt, the output file.

Sample problem 10:

• sparsekit_prb10.f, a sample calling program.
• sparsekit_prb10.sh, commands to compile and run the sample program.
• sparsekit_prb10_output.txt, the output file.

Sample problem 11:

• sparsekit_prb11.f, a sample calling program.
• sparsekit_prb11.sh, commands to compile and run the sample program.
• sparsekit_prb11_output.txt, the output file.

Sample problem 12:

• sparsekit_prb12.f, a sample calling program.
• sparsekit_prb12.sh, commands to compile and run the sample program.
• sparsekit_prb12_output.txt, the output file.

Sample problem 13:

• sparsekit_prb13.f, a sample calling program.
• sparsekit_prb13.sh, commands to compile and run the sample program.
• sparsekit_prb13_output.txt, the output file.

Sample problem 14 generates a sample CSR matrix and converts it to an NCF (nonsymmetric coordinate format) used by NSPCG.

• sparsekit_prb14.f, a sample calling program.
• sparsekit_prb14.sh, commands to compile and run the sample program.
• sparsekit_prb14_output.txt, the output file.

List of Routines:

• AMASK extracts a sparse matrix from a masked input matrix.
• AMUB performs the matrix product C = A * B.
• AMUBDG gets the number of nonzero elements in each row of A * B.
• AMUDIA performs the matrix by matrix product B = A * Diag (in place)
• AMUX multiplies a CSR matrix A times a vector.
• AMUXD multiplies a DIA matrix times a vector.
• AMUXE multiplies an ELL matrix times a vector.
• AMUXJ multiplies a JAD matrix times a vector.
• APLB performs the CSR matrix sum C = A + B.
• APLB1 performs the sum C = A + B for sorted CSR matrices.
• APLBDG gets the number of nonzero elements in each row of A + B.
• APLDIA adds a diagonal matrix to a general sparse matrix: B = A + Diag.
• APLSB performs the matrix linear combination C = A + s * B.
• APLSB1 performs the operation C = A + s * B for sorted CSR matrices.
• APLSBT performs the matrix sum C = A + B'.
• APLSCA adds a scalar to the diagonal entries of a sparse matrix A :=A + s I
• APMBT performs the matrix sum C = A + B' or C = A - B'.
• ASSMB1 assembles a finite element matrix in the CSR format.
• ASSMBO assembles a finite element matrix.
• ATMUX computes A' * x for a CSR matrix A.
• BLKCHK checks whether the input matrix is a block matrix.
• BLKFND determines the block structure of a matrix.
• BNDCSR converts Banded Linpack format to Compressed Sparse Row format.
• BOUND counts the number of boundary points.
• BSORT2 returns the NCUT largest elements of an array, using bubble sort.
• BSRCSR converts Block Sparse Row to Compressed Sparse Row (CSR) format.
• BSTEN calculates block stencil values.
• CHECKREF returns the expected number of new nodes and elements.
• CHKELMT checks the labeling within each element and reorders if necessary.
• CNRMS gets the norms of each column of A.
• COICSR converts COO to CSR in place.
• COOCSR converts COO to CSR.
• COOELL converts coordinate format to Ellpack/Itpack format.
• COPMAT copies the matrix A, JA, IA, into the matrix AO, JAO, IAO.
• CPERM permutes the columns of a matrix.
• CSCAL scales the columns of A such that their norms are one.
• CSORT sorts the elements of a CSR matrix.
• CSRBND converts Compressed Sparse Row to Banded Linpack format.
• CSRBSR converts Compressed Sparse Row to Block Sparse Row.
• CSRCOO converts Compressed Sparse Row to Coordinate format.
• CSRCSC converts Compressed Sparse Row to Compressed Sparse Column.
• CSRDIA converts Compressed Sparse Row to diagonal format.
• CSRDNS converts Compressed Sparse Row to Dense format.
• CSRELL converts Compressed Sparse Row to Ellpack/Itpack format.
• CSRJAD converts Compressed Sparse Row to Jagged Diagonal storage.
• CSRLNK converts Compressed Sparse Row to Linked storage format.
• CSRMSR converts Compressed Sparse Row to Modified Sparse Row.
• CSRNCF converts CSR to NSPCG NCF format.
• CSRSSK converts Compressed Sparse Row to Symmetric Skyline Format.
• CSRSSR converts Compressed Sparse Row to Symmetric Sparse Row.
• DAXPY computes constant times a vector plus a vector.
• DCN generates sparse square matrices of type D(N,C).
• DCSORT computes a sorting permutation for a vector.
• DDOT forms the dot product of two vectors.
• DIACSR converts diagonal format to compressed sparse row.
• DIAMUA performs the matrix by matrix product B = Diag * A.
• DIAPOS returns the positions of the diagonal elements of a sparse matrix.
• DINFO1 computes and prints matrix statistics.
• DIRIC accounts for Dirichlet boundary conditions.
• DLAUNY is a simple, nonoptimal Delaunay triangulation code.
• DNSCSR converts Dense to Compressed Row Sparse format.
• DPERM permutes the rows and columns of a matrix stored in CSR format.
• DSCALDG scales rows by a diagonal factor.
• DUMP writes the matrix to a file.
• DVPERM performs an in-place permutation of a double precision vector.
• ECN generates sparse (square) matrices of the type E(N,C).
• ELLCSR converts Ellpack/Itpack to Compressed Sparse Row.
• ESTIF3 constructs an element stiffness matrix using 3 node triangles.
• EXPHES computes the Arnoldi basis.
• EXPPRO computes an approximation to the vector
• EXPPROD computes an approximation to the vector
• EXTBDG extracts the main diagonal blocks of a matrix.
• FILTER copies a matrix, dropping small elements.
• GEN57BL computes the sparse matrix for an elliptic operator.
• GEN57PT computes the compressed sparse matrix for an elliptic operator.
• GENFEA generates finite element matrices for heat conduction problems.
• GENFEU generates finite element matrices for heat conduction problems.
• GETBWD gets the bandwidth of lower part and upper part of A.
• GETDIA extracts a given diagonal from a matrix stored in CSR format.
• GETELM returns the element A(I,J) of a CSR matrix A.
• GETL extracts the lower triangular part of a matrix.
• GETSTEN calculates the stencil for centered elliptic discretization.
• GETU extracts the upper triangular part of a matrix.
• GRADI3 constructs the first derivative of the shape functions.
• HES computes exp ( H dt) * y where H = Hessenberg matrix (hh)
• HSOURC assembles the load vector F from element contributions in FS.
• ILU0 is an ILU(0) preconditioner.
• ILUT is an ILUT preconditioner.
• INFDIA obtains information on the diagonals of A.
• IVPERM performs an in-place permutation of an integer vector.
• JADSCR converts Jagged Diagonal Storage to Compressed Sparse Row.
• LDSOL solves L * x = y, for L a triangular matrix in MSR format.
• LDSOLC solves L*x = y; L = nonunit Low. Triang. MSC format
• LDSOLL solves L*x = y; L = triangular.
• LEVELS gets the level structure of a lower triangular matrix.
• LNKCSR converts linked list storage to Compressed Sparse Row format.
• LSOL solves L*x = y ; L = lower unit triang. / CSR format
• LSOLC solves L*x = y where L = unit lower triang. CSC format
• LUSOL0 performs forward and backward solves for LU matrix produced by ILUT.
• MARKGEN is a matrix generator for a Markov random walk on a triang. grid
• MATRF2 generates sparse (rectangular or square) matrices.
• MGSR is a modified Gram - Schmidt with partial reorthogonalization.
• MILU0 is a simple milu(0) preconditioner.
• MSRCSR converts Modified Sparse Row to Compressed Sparse Row.
• OPE sparse matrix * vector multiplication
• PGMRES is an ILUT - Preconditioned GMRES solver.
• PLTMT creates a 'pic' plot of a matrix.
• PLTMTPS creates a PostScript plot of a sparse matrix.
• PROJECT computes the matrix-vector product w = U * v.
• PRTMT writes a matrix in Harwell-Boeing format into a file.
• READMT reads a Harwell/Boeing sparse matrix file.
• REFALL refines a finite element grid using triangular elements.
• RETMX returns in dd(*) the max absolute value of elements in row *.
• RNRMS gets the norms of each row of A. (choice of three norms)
• RPERM permutes the rows of a matrix in CSR format.
• RSCAL normalizes the rows of A.
• SSKSSR converts Symmetric Skyline Format to Symmetric Sparse Row format.
• SSRCSR converts Symmetric Sparse Row to (regular) Compressed Sparse Row.
• SUBMAT extracts the submatrix A(i1:i2,j1:j2).
• TIMESTAMP prints out the current YMDHMS date as a timestamp.
• TRANSP carries out in-place transposition routine.
• UDSOL solves U*x = y; U = upper triangular in MSR format
• UDSOLC solves U * x = y, for upper triangular U in MSC format.
• UNASSBL ?
• USOL solves U x = y U = unit upper triangular.
• USOLC solves U * x = y for unit upper triangular U in CSC format.

You can go up one level to the FORTRAN77 source codes.