CG
Conjugate Gradient (CG) Solver for Linear Systems

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

Related Data and Programs:

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

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

FEM2D_POISSON_CG, a FORTRAN90 program which solves Poisson's equation on a triangulated region, using the finite element method (FEM), sparse storage, and a conjugate gradient solver.

SPARSE_DISPLAY, is a FORTRAN90 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 FORTRAN90 library which compares storage schemes (full, banded, sparse triplet) and solution strategies (Linpack full, Linpack banded, 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:

• cg.f90, the source code.

Examples and Tests:

• cg_test.f90, a sample calling program.
• cg_test.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.
• R83_DIF2 returns the DIF2 matrix in R83 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_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_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 the current YMDHMS date as a time stamp.

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