MGMRES
Restarted GMRES solver for sparse linear systems

MGMRES is a FORTRAN77 library which applies the restarted Generalized Minimum Residual (GMRES) algorithm to solve a sparse linear system, using compressed row (CR) or sparse triplet (ST) format, by Lili Ju.

One matrix format used is the ST or "sparse triplet" format, which simply stores NZ_NUM, the number of nonzeros, and stores the K-th nonzero matrix entry as

• A(K), the value of the entry;
• IA(K), the row of the entry;
• JA(K), the column of the entry;

Another matrix format used is the CR or "sparse compressed row" format, which is similar to the sparse triplet format except that it the vector of row indices is compressed to a vector of length N+1 which points to the beginning of the set of entries for each row.

• A(1:NZ_NUM), the value of the entry;
• IA(1:N+1), row I values occur in entries IA(I) to IA(I+1)-1;
• JA(1:NZ_NUM), the column of the entry;

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

MGMRES is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

CC, a data directory which contains examples of the Compressed Column (CC) sparse matrix file format;

CG_RC, a FORTRAN77 library which implements the conjugate gradient method for solving a positive definite sparse linear system A*x=b, using reverse communication.

CR, a data directory which contains examples of the Compressed Row (CR) sparse matrix file format;

HB, a data directory which contains examples of HB files, the Harwell Boeing sparse matrix file format;

HB_READ, a FORTRAN77 library which reads files in the Harwell Boeing (HB) sparse matrix format; This is a simplified interface intended to handle only the most common format, complex unsymmetric assembled (CUA) or real unsymmetric assembled (RUA).

HB_TO_ST, a FORTRAN77 program which converts a sparse matrix from Harwell-Boeing to sparse triplet format.

SPARSEKIT, a FORTRAN77 library which implements operations on sparse matrices, including conversion between various formats, by Yousef Saad.

SPARSEPAK, a FORTRAN77 library which forms an obsolete version of the Waterloo Sparse Matrix Package.

ST, a data directory which contains examples of ST files, the Sparse Triplet format, a sparse matrix file format, storing just (I,J,A(I,J)), and using zero-based indexing.

SUPERLU, FORTRAN77 programs which illustrate how to use the SUPERLU library, which applies a fast direct solution method to solve sparse linear systems, by James Demmel, John Gilbert, and Xiaoye Li.

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

Author:

Original C version by Lili Ju, Mathematics Department, University of South Carolina; FORTRAN77 version by John Burkardt.

Reference:

1. Richard Barrett, Michael Berry, Tony Chan, James Demmel, June Donato, Jack Dongarra, Victor Eijkhout, Roidan Pozo, Charles Romine, Henk van der Vorst,
   Templates for the Solution of Linear Systems:
   Building Blocks for Iterative Methods,
   SIAM, 1994,
   ISBN: 0898714710,
   LC: QA297.8.T45.
2. Tim Kelley,
   Iterative Methods for Linear and Nonlinear Equations,
   SIAM, 2004,
   ISBN: 0898713528,
   LC: QA297.8.K45.
3. Yousef Saad,
   Iterative Methods for Sparse Linear Systems,
   Second Edition,
   SIAM, 20003,
   ISBN: 0898715342,
   LC: QA188.S17.

Source Code:

• mgmres.f, the source code.
• mgmres.csh, commands to compile the source code.

Examples and Tests:

• mgmres_prb.f, a sample calling program.
• mgmres_prb.csh, commands to compile and run the sample program.
• mgmres_prb_output.txt, the output file.

List of Routines:

• ATX_CR computes A'*x for a matrix stored in sparse compressed row form.
• ATX_ST computes A'*x for a matrix stored in sparset triplet form.
• AX_CR computes A*x for a matrix stored in sparse compressed row form.
• AX_ST computes A*x for a matrix stored in sparset triplet form.
• DIAGONAL_POINTER_CR finds diagonal entries in a sparse compressed row matrix.
• ILU_CR computes the incomplete LU factorization of a matrix.
• LUS_CR applies the incomplete LU preconditioner.
• MGMRES_ST applies restarted GMRES to a sparse triplet matrix.
• MULT_GIVENS applies a Givens rotation to two successive entries of a vector.
• PMGMRES_ILU_CR applies the preconditioned restarted GMRES algorithm.
• R8VEC_DOT_PRODUCT finds the dot product of a pair of R8VEC's.
• R8VEC_NORM returns the L2 norm of an R8VEC.
• R8VEC_UNIFORM_01 returns a unit pseudorandom R8VEC.
• REARRANGE_CR sorts a sparse compressed row matrix.
• TIMESTAMP prints out the current YMDHMS date as a timestamp.

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