cg

cg, an Octave code which implements a simple version of the conjugate gradient (CG) method for solving a system of linear equations of the form A*x=b, suitable for situations in which the matrix A is positive definite (only real, positive eigenvalues) and symmetric.

Licensing:

The computer code and data files made available on this web page are distributed under the MIT license

Languages:

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

Related Data and Programs:

cg_test

bicg, an Octave code which implements the biconjugate gradient method (BICG), which estimates the solution of a large sparse nonsymmetric linear system.

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

cg_squared, an Octave code which implements the conjugate gradient squared (CGS) method for solving a nonsymmetric sparse linear system A*x=b.

cgne, an Octave code which implements the conjugate gradient method (CG) for the normal equations, that is, a method for solving a system of linear equations of the form A*x=b, where the matrix A is not symmetric positive definite (SPD). In this case, it is attempted to set up and solve the normal equations A'*A*x=A'*b.

gmres, an Octave code which applies the Generalized Minimum Residual (GMRES) method to solve a nonsymmetric sparse linear system.

sor, an Octave code which implements a simple version of the successive over-relaxation (SOR) method for the iteration solution of a linear system of equations.

wathen_matrix, an Octave code which compares storage schemes (full, banded, sparse triplet, sparse) and solution strategies (A\x, Linpack, conjugate gradient) for linear systems involving the Wathen matrix, which can arise when solving a problem using the finite element method (FEM).

Reference:

1. Frank Beckman,
   The Solution of Linear Equations by the Conjugate Gradient Method,
   in Mathematical Methods for Digital Computers,
   edited by John Ralston, Herbert Wilf,
   Wiley, 1967,
   ISBN: 0471706892,
   LC: QA76.5.R3.
2. Jonathan Shewchuk,
   An introduction to the conjugate gradient method without the agonizing pain, Edition 1.25, August 1994.

Source Code:

• orth_random.m, returns the ORTH_RANDOM matrix.
• r8_sign.m, returns the sign of an R8.
• r83_cg.m, uses the conjugate gradient method on an R83 system.
• r83_dif2.m, returns the DIF2 matrix in R83 format.
• r83_mv.m, multiplies an R83 matrix times an R8VEC.
• r83_res.m, computes the residual R = B-A*X for R83 matrices.
• r83s_cg.m, uses the conjugate gradient method on an R83S system.
• r83s_dif2.m, returns the DIF2 matrix in R83S format.
• r83s_mv.m, multiplies an R83S matrix times an R8VEC.
• r83s_res.m, computes the residual R = B-A*X for R83S matrices.
• r83t_cg.m, uses the conjugate gradient method on an R83T system.
• r83t_dif2.m, returns the DIF2 matrix in R83T format.
• r83t_mv.m, multiplies an R83T matrix times an R8VEC.
• r83t_res.m, computes the residual R = B-A*X for R83T matrices.
• r8ge_cg.m, uses the conjugate gradient method on an R8GE system.
• r8ge_dif2.m, returns the DIF2 matrix in R8GE format.
• r8ge_mv.m, multiplies an R8GE matrix by an R8VEC.
• r8ge_res.m, computes the residual R = B-A*X for R8GE matrices.
• r8mat_house_axh.m, computes A*H where H is a compact Householder matrix.
• r8mat_print.m, prints an R8MAT.
• r8mat_print_some.m, prints some of an R8MAT.
• r8pbu_cg.m, uses the conjugate gradient method on an R8PBU system.
• r8pbu_dif2.m, returns the DIF2 matrix in R8PBU format.
• r8pbu_mv.m, multiplies an R8PBU matrix by an R8VEC.
• r8pbu_res.m, computes the residual R = B-A*X for R8PBU matrices.
• r8sd_cg.m, uses the conjugate gradient method on an R8SD linear system.
• r8sd_dif2.m, returns the DIF2 matrix in R8SD format.
• r8sd_mv.m, multiplies an R8SD matrix by an R8VEC.
• r8sd_res.m, computes the residual R = B-A*X for R8SD matrices.
• r8sp_cg.m, uses the conjugate gradient method on an R8SP system.
• r8sp_dif2.m, returns the DIF2 matrix in R8SP format.
• r8sp_mv.m, multiplies an R8SP matrix by an R8VEC.
• r8sp_res.m, computes the residual R = B-A*X for R8SP matrices.
• r8vec_house_column.m, defines a Householder premultiplier that "packs" a column.
• r8vec_print.m, prints an R8VEC.
• spd_random.m, returns the spd_random() matrix.