MGMRES
Restarted GMRES solver for sparse linear systems

MGMRES is a MATLAB 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 DSP 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:

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

DLAP, a FORTRAN90 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 format.

KELLEY, a MATLAB library which implements iterative methods for linear and nonlinear equations, by Tim Kelley;

LINPACK, a FORTRAN90 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 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.

SPARSEKIT, a FORTRAN90 library which implements operations on sparse matrices, including conversion between various formats.

ST, a data directory which contains a description and examples of the 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.

TEMPLATES, a FORTRAN90 library which carries out simple versions of various iterative solvers.

TEST_MAT, a MATLAB library which defines test matrices.

Author:

Original C version by Lili Ju, Mathematics Department, University of South Carolina; Matlab 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:

• atx_cr.m computes A'*x for a matrix stored in sparse compressed row form.
• atx_st.m, computes A'*x for a matrix stored in sparse triplet form..
• ax_cr.m computes A*x for a matrix stored in sparse compressed row form.
• ax_st.m, computes A*x for a matrix stored in sparse triplet form..
• diagonal_pointer_cr.m, finds diagonal entries in a sparse compressed row matrix.
• ilu_cr.m, computes the incomplete LU preconditioner.
• lus_cr.m, applies the incomplete LU preconditioner.
• mgmres_st.m, carries out the restarted GMRES algorithm for a matrix in sparse triplet form.
• mult_givens.m, applies a Givens rotation.
• r8vec_uniform_01.m, returns a unit pseudorandom R8VEC.
• rearrange_cr.m, sorts a sparse compressed row matrix.
• timestamp.m, prints the YMDHMS date as a timestamp.

Examples and Tests:

• mgmres_test.m, calls all the tests.
• mgmres_test01.m, tests MGMRES_ST on the -1,2,-1 matrix.
• mgmres_test02.m, tests MGMRES_ST on a more interesting matrix.
• mgmres_test_output.txt, the output file.

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