Linear conjugate gradient

When one refers to the CG method, one often means the linear conjugate gradient, that is, the implementation for the convex quadratic form. In this case, minimizing IxTAx + bTx is equivalent to solving the linear system Ax = -b. Consequently, the conjugate directions pfe, as well as the lengths kh, can be computed in closed form. 

Newman, G. A., and D. L. Alumbaugh, 2000, Three-dimensional magnetotelluric inversion using non-linear conjugate gradients Geophys. J. Int., 140, 410-424. 

The Hessian-vector products in each linear conjugate gradient step are more significant. For a Hessian formulated with a nonbonded cutoff radius (e.g., 8 A), many zeros result for the Hessian (see Figure 3) when this sparsity is exploited in the multiplication routine, performance is fast compared with a dense matrix-vector product. When the Hessian is dense and large in size, the following forward-difference formula of two gradients often works faster ... 

Davis, M. E., McCammon, J. A. Solving the finite difference linearized Poisson-Boltzmann equation A comparison of relaxation and conjugate gradients methods.. J. Comp. Chem. 10 (1989) 386-394. 

McIntosh, A. Fitting Linear Models An Application of Conjugate Gradient Algorithms, Springer-Verlag, New York (1982). 

In CED, a number of different iterative solvers for linear algebraic systems have been applied. Two of the most successful and most widely used methods are conjugate gradient and multigrid methods. The basic idea of the conjugate gradient method is to transform the linear equation system Eq. (38) into a minimization problem... 

Millam, J. M., Scuseria, G. E., 1997, Linear Scaling Conjugate Gradient Density Matrix Search as an Alternative to Diagonalization for First Principles Electronic Structure Calculations , J. Chem. Phys., 106, 5569. 

Sparse matrices are ones in which the majority of the elements are zero. If the structure of the matrix is exploited, the solution time on a computer is greatly reduced. See Duff, I. S., J. K. Reid, and A. M. Erisman (eds.), Direct Methods for Sparse Matrices, Clarendon Press, Oxford (1986) Saad, Y., Iterative Methods for Sparse Linear Systems, 2d ed., Society for Industrial and Applied Mathematics, Philadelphia (2003). The conjugate gradient method is one method for solving sparse matrix problems, since it only involves multiplication of a matrix times a vector. Thus the sparseness of the matrix is easy to exploit. The conjugate gradient method is an iterative method that converges for sure in n iterations where the matrix is an n x n matrix. 

The set of Kohn-Sham-like linear equations above represents the working equations of DFPT. They are usually solved by iterative linear algebra algorithms (conjugate-gradient minimization). 

Similar information to that obtained dining a conjugate gradient refinement is obtainable from second derivatives (curvature)1 R 51 93. For a harmonic function the gradient (linear matrix of first derivatives, [A]) multiplied by the curvature (Hessian matrix of second derivatives, [C]) should lead directly to the shifts (AX) to be applied in order to move toward the minimum (Eq. 3.3). 

Beckman FS (1960) The solution of linear equations by conjugate gradient method In Ralston A, Wilf HS (eds) (1960) Mathematical methods for digital computers 1, chap 4. Wiley, New York, p 62-67... 

Kammerer WJ, Nashed MZ (1972) On the convergence of the conjugate gradient method for singular linear operator equations. SIAM J Numer Anal 9 165-181... 

The Polak-Ribiere conjugate gradient method " was used in RSll to perform the non-linear mnlhvariate optimization of the objective function with the weighing factors, Wj = 1 and W2 = 10. 

---