CG
Conjugate Gradient Solver for Linear Systems

CG is a Python 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 Python library which implements the conjugate gradient (CG) method for solving a positive definite sparse linear system A*x=b, using reverse communication (RC).

GMGSOLVE, a Python library which can apply one step of the V-cycle of the geometric multigrid method, by Mike Sussman.

JACOBI, a Python library which implements the Jacobi iteration for solving symmetric positive definite (SPD) systems of linear equations.

SOLVE, a Python library which demonstrates how Gauss elimination can be used to solve a simple system of linear equations A*x=b.

TEST_MAT, a Python library which defines test matrices, some of which have known determinants, eigenvalues and eigenvectors, inverses and so on.

WATHEN, a Python library 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.py, returns the ORTH_RANDOM matrix.
• pds_random.py, returns the PDS_RANDOM matrix.
• r8_normal_01.py, returns a unit pseudonormal R8.
• r8_uniform_01.py, returns a unit pseudorandom R8.
• r83_subset.py, a subset of the R83 library from LINPLUS, containing those functions needed for a conjugate gradient calculation.
• r83s_subset.py, a subset of the R83S library from LINPLUS, containing those functions needed for a conjugate gradient calculation.
• r83t_subset.py, a subset of the R83T library from LINPLUS, containing those functions needed for a conjugate gradient calculation.
• r8ge_subset.py, a subset of the R8GE library from LINPLUS, containing those functions needed for a conjugate gradient calculation.
• r8mat_house_axh.py, computes A*H where H is a compact Householder matrix.
• r8mat_house_form.py, constructs a Householder matrix from its compact form.
• r8mat_mm.py, computes a matrix-matrix product of two R8MAT's.
• r8mat_print.py, prints an R8MAT.
• r8mat_print_some.py, prints some of an R8MAT.
• r8pbu_subset.py, a subset of the R8PBU library from LINPLUS, containing those functions needed for a conjugate gradient calculation.
• r8sd_subset.py, a subset of the R8SD library from LINPLUS, containing those functions needed for a conjugate gradient calculation.
• r8sp_subset.py, a subset of the R8SP library from LINPLUS, containing those functions needed for a conjugate gradient calculation.
• r8vec_house_column.py, defines a Householder premultiplier that "packs" a column.
• r8vec_norm.py, returns the L2 norm of an R8VEC.
• r8vec_norm_affine.py, returns the L2 norm of the difference of R8VEC's.
• r8vec_print.py, prints an R8VEC.
• r8vec_uniform_01.py, returns a unit pseudorandom R8VEC.
• r8vec_uniform_ab.py, returns a scaled pseudorandom R8VEC.
• timestamp.py, prints the current YMDHMS date as a time stamp.

Examples and Tests:

• cg_test.py, calls all the tests.
• cg_test.sh, runs all the tests.
• cg_test.txt, the output file.

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