cPCG (version 1.0)

cgsolve: Conjugate gradient method

Description

Conjugate gradient method for solving system of linear equations Ax = b, where A is symmetric and positive definite, b is a column vector.

Usage

cgsolve(A, b, tol = 1e-6, maxIter = 1000)

Arguments

A

matrix, symmetric and positive definite.

b

vector, with same dimension as number of rows of A.

tol

numeric, threshold for convergence, default is 1e-6.

maxIter

numeric, maximum iteration, default is 1000.

Value

Returns a vector representing solution x.

Warning

Users need to check that input matrix A is symmetric and positive definite before applying the function.

Details

The idea of conjugate gradient method is to find a set of mutually conjugate directions for the unconstrained problem $$ arg min_x f(x)$$ where \(f(x) = 0.5 b^T A b - bx + z\) and \(z\) is a constant. The problem is equivalent to solving \(Ax = b\).

This function implements an iterative procedure to reduce the number of matrix-vector multiplications [1]. The conjugate gradient method improves memory efficiency and computational complexity, especially when \(A\) is relatively sparse.

References

[1] Yousef Saad. Iterative methods for sparse linear systems. Vol. 82. siam, 2003.

See Also

pcgsolve

Examples

# NOT RUN {
test_A <- matrix(c(4,1,1,3), ncol = 2)
test_b <- matrix(1:2, ncol = 1)
cgsolve(test_A, test_b, 1e-6, 1000)
# }