MGMRES
Restarted GMRES solver for sparse linear systems

MGMRES is a C library which applies a simple restarted GMRES iteration to a sparse linear system stored in a simple format, by Lili Ju.

One matrix format used is the sparse triplet (ST) 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 compressed row (CR) format, which is similar to the sparse triplet format except that 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:

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

CSPARSE, a C library which implements iterative methods for solving linear systems.

DSP, a data directory which contains a description and examples of the DSP format for storing sparse matrices, which is used by the FORTRAN90 version of MGMRES.

HBSMC, a dataset directory which contains a collection of large sparse matrices stored in the Harwell-Boeing (HB) format.

LINPACK_D, a C library which carries out direct methods for solving linear systems.

MM, a data directory which contains a description and examples of the Matrix Market format for storing matrices.

SPARSE_CC, a data directory which contains a description and examples of the compressed column (CC) 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 compressed row (CR) for storing a sparse matrix, including a way to write the matrix as a set of three files.

ST, a data directory which contains a description and examples of the sparse triplet (ST) format for storing sparse matrices, which used by the C and C++ versions of mgmres.

SUPER_LU, a C program which applies a fast direct solution method to a sparse linear system.

TEST_MAT, a C library which defines test matrices.

Author:

Original C version by Lili Ju, Mathematics Department, University of South Carolina; this C 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.c, the source code.
• mgmres.h, the include file.
• mgmres.sh, commands to compile the source code.

Examples and Tests:

• mgmres_prb.c, a sample calling program.
• mgmres_prb.sh, 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 sparse 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 sparse triplet form.
• DIAGONAL_POINTER_CR finds diagonal entries in a sparse compressed row matrix.
• DMATRIX allocates a double matrix with subscript range m[nrl..nrh][ncl..nch]
• FREE_DMATRIX frees a double matrix allocated by DMATRIX.
• ILU_CR computes the incomplete LU factorization of a matrix.
• LUS_CR applies the incomplete LU preconditioner.
• MGMRES_ST applies restarted GMRES to a matrix in sparse triplet form.
• MULT_GIVENS applies a Givens rotation to two vector elements.
• PMGMRES_ILU_CR applies the preconditioned restarted GMRES algorithm.
• R8VEC_DOT computes the dot product of a pair of R8VEC's.
• R8VEC_UNIFORM_01 fills a double precision vector with unit pseudorandom values.
• REARRANGE_CR sorts a sparse compressed row matrix.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

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