mgmres

mgmres, a MATLAB code which applies the restarted Generalized Minimum Residual (GMRES) algorithm to solve a sparse linear system, using compressed row storage (CRS) 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 CRS or "compressed row storage" 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 MIT license.

Languages:

mgmres is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version.

Related Data and Programs:

mgmres_test

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

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

crs_io, a MATLAB code which reads and writes sparse linear systems stored in the Compressed Row Storage (CRS) format.

hbsmc, a dataset directory which contains a collection of large sparse matrices stored in the Harwell-Boeing format.

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

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

st, a data directory which contains a description and examples of the ST format for storing sparse matrices.

st_io, a MATLAB code which reads and writes sparse linear systems stored in the Sparse Triplet (ST) format.

test_matrix, a MATLAB code 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_crs.m computes A'*x for a matrix stored in CRS form.
• atx_st.m, computes A'*x for a matrix stored in ST form.
• ax_crs.m computes A*x for a matrix stored in CRS form.
• ax_st.m, computes A*x for a matrix stored in ST form.
• diagonal_pointer_crs.m, finds diagonal entries in a CRS matrix.
• ilu_crs.m, computes the incomplete LU preconditioner for a CRS matrix.
• lus_crs.m, applies the incomplete LU preconditioner for a CRS matrix.
• mgmres_st.m, carries out the restarted GMRES algorithm for a matrix in ST form.
• mult_givens.m, applies a Givens rotation.
• r8vec_uniform_01.m, returns a unit pseudorandom R8VEC.
• rearrange_crs.m, sorts a CRS matrix.