SPARSEKIT
Sparse Matrix Utility Package

SPARSEKIT is a FORTRAN90 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.

Formats recognized by SPARSKIT 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.

Related Data and Programs:

CSPARSE is a C library of routines for direct sparse matrix operations.

DLAP is a library of FORTRAN90 routines for solving sparse linear systems.

HB_IO is a library of FORTRAN90 routines for reading and writing sparse linear systems stored in the Harwell-Boeing Sparse Matrix format.

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

MGMRES is a FORTRAN90 routine which applies the restarted GMRES algorithm to solve a sparse linear system.

MM_IO is a set of FORTRAN90 routines for reading and writing sparse linear systems stored in the Matrix Market format.

NSPCG is a library of FORTRAN90 routines for nonsymmetric preconditioned conjugate gradient methods applied to sparse matrices.

PETSC, is a scientific library for use in parallel computation, which includes an implementation of the BLAS1 routines.

SPARSE is a built-in MATLAB function for defining sparse matrices.

SPARSE_CC is 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 is 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.

SPARSEPAK is a set of FORTRAN90 routines for reordering sparse matrices.

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.f90, the source code.
• sparsekit.csh, commands to compile the source code.

Examples and Tests:

Sample problem 1:

• sparsekit_prb01.f90, a sample calling program.
• sparsekit_prb01.csh, commands to compile and run the sample program.
• sparsekit_prb01_output.txt, the output from a run of the sample program.

Sample problem 2:

• sparsekit_prb02.f90, a sample calling program.
• sparsekit_prb02.csh, commands to compile and run the sample program.
• sparsekit_prb02_output.txt, the output from a run of the sample program.

Sample problem 3:

• sparsekit_prb03.f90, a sample calling program.
• sparsekit_prb03.csh, commands to compile and run the sample program.
• sparsekit_prb03_output.txt, the output from a run of the sample program.

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.f90, a sample calling program.
• sparsekit_prb04.csh, commands to compile and run the sample program.
• sparsekit_prb04_output.txt, the output from a run of the sample program.

Sample problem 5:

• sparsekit_prb05.f90, a sample calling program.
• sparsekit_prb05.csh, commands to compile and run the sample program.
• sparsekit_prb05_output.txt, the output from a run of the sample program.

Sample problem 6:

• sparsekit_prb06.f90, a sample calling program.
• sparsekit_prb06.csh, commands to compile and run the sample program.
• sparsekit_prb06_output.txt, the output from a run of the sample program.

Sample problem 7:

• sparsekit_prb07.f90, a sample calling program.
• sparsekit_prb07.csh, commands to compile and run the sample program.
• sparsekit_prb07_output.txt, the output from a run of the sample program.

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

• sparsekit_prb08.f90, a sample calling program.
• sparsekit_prb08.csh, commands to compile and run the sample program.
• sparsekit_prb08_output.txt, the output from a run of the sample program.
• 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.f90, a sample calling program.
• sparsekit_prb09.csh, commands to compile and run the sample program.
• sparsekit_prb09_output.txt, the output from a run of the sample program.

Sample problem 10:

• sparsekit_prb10.f90, a sample calling program.
• sparsekit_prb10.csh, commands to compile and run the sample program.
• sparsekit_prb10_output.txt, the output from a run of the sample program.

Sample problem 11:

• sparsekit_prb11.f90, a sample calling program.
• sparsekit_prb11.csh, commands to compile and run the sample program.
• sparsekit_prb11_output.txt, the output from a run of the sample program.

Sample problem 12:

• sparsekit_prb12.f90, a sample calling program.
• sparsekit_prb12.csh, commands to compile and run the sample program.
• sparsekit_prb12_output.txt, the output from a run of the sample program.

Sample problem 13:

• sparsekit_prb13.f90, a sample calling program.
• sparsekit_prb13.csh, commands to compile and run the sample program.
• sparsekit_prb13_output.txt, the output from a run of the sample program.

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

• sparsekit_prb14.f90, a sample calling program.
• sparsekit_prb14.csh, commands to compile and run the sample program.
• sparsekit_prb14_output.txt, the output from a run of the sample program.

List of Routines:

• AMASK extracts a sparse matrix from a masked input matrix.
• AMUB performs the matrix by 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 matrix sum C = A+B for matrices in sorted CSR format.
• APLBDG gets the number of nonzero elements in each row of A+B and the total
• 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 matrices in sorted CSR format.
• 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 ???
• ASSMBO ???
• ATMUX computes A' * x for a CSR matrix A.
• BLKCHK checks whether the input matrix is a block
• BLKFND attemptps to determine whether or not the input
• BNDCSR converts Banded Linpack format to Compressed Sparse Row format.
• BOUND counts the number of boundary points and
• BSORT2 simple bubble sort for getting the ncut largest
• BSRCSR converts Block Sparse Row to Compressed Sparse Row.
• BSTEN calculates the correct block-stencil values for
• CHECKREF returns the expected the new number of nodes and
• CHKELMT checks the labeling within each element and reorders
• CNRMS gets the norms of each column of A. (choice of three norms)
• COICSR converts COO to CSR in place.
• COOCSR converts COO to CSR.
• COOELL converts coordinate format to ellpack 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 on return
• CSORT sorts the elements of a matrix (stored in Compressed
• 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
• CSRCSC converts Compressed Sparse Row to Compressed Sparse Column
• CSRDIA converts Compressed sparse row to diagonal format
• CSRDNS converts Compressed Sparse Row to Dense
• 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
• CSRSSK converts Compressed Sparse Row to Symmetric Skyline Format
• CSRSSR converts Compressed Sparse Row to Symmetric Sparse Row
• DCN generates sparse square matrices of type D(N,C).
• DCSORT computes a permutation which, when applied to the
• DIACSR converts diagonal format to compressed sparse row
• DIAMUA performs the matrix by matrix product B = Diag * A (in place)
• DIAPOS returns the positions of the diagonal elements of a
• DINFO1 computes and prints matrix statistics.
• DIRIC takes into account the boundary conditions
• DLAUNY is a simple, nonoptimal Delaunay triangulation code.
• DNSCSR converts Dense to Compressed Row Sparse
• DPERM permutes the rows and columns of a matrix stored in CSR
• DSCALDG scales rows by diag where diag is either given (job=0)
• DUMP writes the matrix in a file, one row at a time in a nice readable
• DVPERM performs an in-place permutation of a real vector x
• ECN generates sparse (square) matrices of the type E(N,C).
• ELLCSR converts Ellpack-Itpack to Compressed Sparse Row.
• ESTIF3 constructs the element stiffness matrix using 3-node triangular elements
• EXPHES computes the Arnoldi basis and the corresponding
• EXPPRO computes an approximation to the vector
• EXPPROD computes an approximation to the vector
• EXTBDG extracts the main diagonal blocks of a
• FILTER removes any elements whose absolute value
• GEN57BL computes the sparse matrix in compressed
• GEN57PT computes the sparse matrix in compressed
• GENFEA generates finite element matrices for heat
• GENFEU generates finite element matrices for heat
• GETBWD gets the bandwidth of lower part and upper part of A.
• GETDIA extracts a given diagonal from a matrix stored in CSR
• GETELM returns the element a(i,j) of a matrix A,
• GETL extracts the lower triangular part of a matrix
• GETSTEN calculates the correct stencil values for
• GETU extracts the upper triangular part of a matrix
• GRADI3 constructs the first derivative of the shape functions.
• HES computes exp ( H dt) * y (1)
• HSOURC generates the load vector f in assembled form from the
• 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 L = triangular. MSR format
• LDSOLC solves L x = y ; L = nonunit Low. Triang. MSC format
• LDSOLL solves L x = y L = triangular. Uses LEVEL SCHEDULING/MSR format
• LEVELS gets the level structure of a lower triangular matrix
• LNKCSR converts linked list storage format 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 trang. CSC format
• LUSOL0 performs a forward followed by a backward solve
• MARKGEN is a matrix generator for a markov model of a random walk on a triang. grid
• MATRF2 generates sparse (rectangular or square) matrices.
• MGSR is a modified gram - schmidt with partial reortho.
• MILU0 is a simple milu(0) preconditioner. *** *
• MSRCSR converts Modified - Sparse Row to Compressed Sparse Row
• PGMRES is an ILUT - Preconditioned GMRES solver.
• PLTMT creates a 'pic' file for plotting the pattern of
• PLTMTPS creates a 'PS' file for plotting the pattern of
• PRTMT writes a matrix in Harwell-Boeing format into a file.
• READMT reads a boeing/harwell matrix. handles right hand
• 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 scales the rows of A such that their norms are one on return
• 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) and puts the result in
• TRANSP carries out in-place transposition routine.
• UDSOL solves U x = y ; U = upper triangular in MSR format
• UDSOLC Solves U x = y ; U = nonunit Up. Triang. MSC format
• UNASSBL ???
• USOL solves U x = y U = unit upper triangular.
• USOLC solves U x = y ; where U = unit upper trang. CSC format
• SAXPY CONSTANT TIMES A VECTOR PLUS A VECTOR.
• SDOT FORMS THE DOT PRODUCT OF TWO VECTORS.

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