CG
Conjugate Gradient Solver for Linear Systems

CG is a FORTRAN77 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 and a Python version.

Related Data and Programs:

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

CG_SERIAL, a FORTRAN77 program which a serial version of the NAS Conjugate Gradient (CG) Parallel Benchmark.

SPARSE_DISPLAY, a FORTRAN77 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 FORTRAN77 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.f, the source code.
• cg.sh, BASH commands to compile the source code.

Examples and Tests:

• cg_prb.f, 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:

• ORTH_RANDOM returns the ORTH_RANDOM matrix.
• PDS_RANDOM returns the PDS_RANDOM matrix.
• R8_NORMAL_01 returns a unit pseudonormal 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 an R83 matrix times an R8VEC.
• 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 an R83S matrix times an R8VEC.
• 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 an R83T matrix times an R8VEC.
• 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_HOUSE_AXH computes A*H where H is a compact Householder matrix.
• R8MAT_MV multiplies a matrix times a vector.
• R8MAT_PRINT prints an R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8PBU_CG uses the conjugate gradient method on an R8PBU system.
• R8PBU_DIF2 returns the DIF2 matrix in R8PBU format.
• R8PBU_MV multiplies an R8PBU matrix by an R8VEC.
• R8PBU_RESID computes the residual R = B-A*X for R8PBU matrices.
• R8SD_CG uses the conjugate gradient method on an R8SD linear system.
• R8SD_DIF2 returns the DIF2 matrix in R8SD format.
• R8SD_MV multiplies an R8SD matrix by an R8VEC.
• R8SD_RESID computes the residual R = B-A*X for R8SD matrices.
• R8SP_CG uses the conjugate gradient method on an R8SP system.
• R8SP_DIF2 returns the DIF2 matrix in R8SP format.
• R8SP_MV multiplies an R8SP matrix by an R8VEC.
• R8SP_RESID computes the residual R = B-A*X for R8SP matrices.
• R8VEC_DIFF_NORM returns the L2 norm of the difference of R8VEC's.
• R8VEC_DOT_PRODUCT finds 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 returns a unit pseudorandom R8VEC.
• TIMESTAMP prints out the current YMDHMS date as a timestamp.

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