CG
Conjugate Gradient Solver for Linear Systems

CG is a C++ library 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 GNU LGPL license.

Languages:

CG 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 (CG) method for solving a positive definite sparse linear system A*x=b, using reverse communication (RC).

LINPLUS, a C++ library which carries out operations such as matrix-vector products, matrix factorization, linear solvers including Gauss-elimination, Jacobi iteration, Gauss-Seidel iteration, Conjugate Gradient (CG), for matrices in a variety of formats, including banded, border-banded, circulant, lower triangular, pentadiagonal, sparse, symmetric, toeplitz, tridiagonal, upper triangular and vandermonde formats.

SPARSE_DISPLAY, a C++ library which can read information defining a matrix of numbers and display the sparsity pattern or location of the nonzero elements using gnuplot. This operation is already available in the built-in MATLAB "spy" command.

WATHEN, a C++ library which compares storage schemes (full, banded, sparse triplet) and solution strategies (Linpack full, Linpack banded, conjugate gradient (CG)) 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:

• cg.cpp, the source code.
• cg.hpp, the include file.
• cg.sh, BASH commands to compile the source code.

Examples and Tests:

• cg_prb.cpp a sample calling program.
• cg_prb.sh, BASH commands to compile and run the sample program.
• cg_prb_output.txt, the output file.

List of Routines:

• I4_MIN returns the minimum of two I4's.
• ORTH_RANDOM returns the ORTH_RANDOM matrix.
• PDS_RANDOM returns the PDS_RANDOM matrix.
• R8_NORMAL_01 samples the standard normal probability distribution.
• R8_SIGN returns the sign of an R8.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• R83_CG uses the conjugate gradient method on an R83 system.
• R83_DIF2 returns the DIF2 matrix in R83 format.
• R83_MV multiplies a R83 matrix times a vector.
• R83_RESID computes the residual R = B-A*X for R83 matrices.
• R83S_CG uses the conjugate gradient method on an R83S system.
• R83S_DIF2 returns the DIF2 matrix in R83S format.
• R83S_MV multiplies a R83S matrix times a vector.
• R83S_RESID computes the residual R = B-A*X for R83S matrices.
• R83T_CG uses the conjugate gradient method on an R83T system.
• R83T_DIF2 returns the DIF2 matrix in R83T format.
• R83T_MV multiplies a R83T matrix times a vector.
• R83T_RESID computes the residual R = B-A*X for R83T matrices.
• R8GE_CG uses the conjugate gradient method on an R8GE system.
• R8GE_DIF2 returns the DIF2 matrix in R8GE format.
• R8GE_MV multiplies an R8GE matrix by an R8VEC.
• R8GE_RESID computes the residual R = B-A*X for R8GE matrices.
• R8MAT_COPY copies one R8MAT to another.
• R8MAT_HOUSE_AXH computes A*H where H is a compact Householder matrix.
• R8MAT_IDENTITY_NEW returns an identity matrix.
• R8MAT_PRINT prints an R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8MAT_ZERO_NEW returns a new zeroed R8MAT.
• R8PBU_CG uses the conjugate gradient method on a R8PBU system.
• R8PBU_DIF2 returns the DIF2 matrix in R8PBU format.
• R8PBU_MV multiplies a R8PBU matrix times a vector.
• R8PBU_RESID computes the residual R = B-A*X for R8PBU matrices.
• R8SD_CG uses the conjugate gradient method on a R8SD linear system.
• R8SD_DIF2 returns the DIF2 matrix in R8SD format.
• R8SD_MV multiplies a R8SD matrix times a vector.
• R8SD_RESID computes the residual R = B-A*X for R8SD matrices.
• R8SP_CG uses the conjugate gradient method on a R8SP linear system.
• R8SP_DIF2 returns the DIF2 matrix in R8SP format.
• R8SP_MV multiplies a R8SP matrix times a vector.
• R8SP_RESID computes the residual R = B-A*X for R8SP matrices.
• R8VEC_COPY copies an R8VEC.
• R8VEC_DIFF_NORM returns the L2 norm of the difference of R8VEC's.
• R8VEC_DOT_PRODUCT computes the dot product of a pair of R8VEC's.
• R8VEC_HOUSE_COLUMN defines a Householder premultiplier that "packs" a column.
• R8VEC_NORM returns the L2 norm of an R8VEC.
• R8VEC_PRINT prints an R8VEC.
• R8VEC_UNIFORM_01_NEW returns a new unit pseudorandom R8VEC.
• R8VEC_ZERO_NEW creates and zeroes an R8VEC.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

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