# 2.7.6 - Florida Institute of Technology 2.7.6 Conjugate Gradient Method for a Sparse Sy stem Shi & Bo What is sparse system A system of linear equations is called sparse if only a relatively small number of its matrix elements are n

onzero. It is wasteful to use general methods of line ar algebra on such problems, because most of the O () arithmetic operations devoted to solving the set of equations or inverting the matrix involve zero opera nds. Furthermore, you might wish to work problems so large as to tax your available memory space, and it is wasteful to reserve storage for unfruitful zero el ements. Note that there are two distinct (and not al ways compatible) goals for any sparse matrix metho

d: saving time and/or saving space. Conjugate Gradient Method Ax=b The ordinary conjugate gradient algorithm: steepest descent method steepest descent method

Where A is n*n symmetric positive definit e matrix, b is known n-d vector. Solving Ax=b is equivalent to minimizing f=Ax-b steepest descent method Steepest Descent

Start at a initial guess point adjust until close en ough to the exact solution: Where i is number of iterations is step size, is A djustment Direction. How to choose direction and step size?

Choose direction Choose the direction which f decreases mos t quickly. Move from point to the point by minimizing along the line from in the direc tion opposite to . Hense, .

Choose step size Step size should minimize f, along the dire ction of ,which means When to stop should give a stopping criterion because We

there may have many errors and noises. (1) only for exact arithmetic, not in practice (2) in practice unstable alg for general A stopping criterion is or with an given small . Symmetric but non-positive definite A With the choice instead of . In this case a

nd for all k. This algorithm is equivalent t o the ordinary conjugate gradient algorith m, but with all dot products replaced by . It is called the minimum residual algorith m, because it corresponds to successive m inimizations of the function any nonsingular matrix A, is symmetric For

and positive-definite. But we cant use . Because the condition number of the matri x is the square of the condition number of A. Thanks Reference Numerical Recipes

Steepest Decent and Conjugate Gradients, w3.pppl.gov/m3d/reference/SteepestDecent andCG.ppt Reference Numerical Recipes Steepest Decent and Conjugate Gradients