In today's post I continue discussing the method of Conjugate Gradients. We talked about preconditioning which is a technique for improving the condition number of a matrix. We tried to do  this by first approximating A with M.  M is a symmetric positive definite matrix which when inverted and applied to A  helps indirectly solve the linear matrix equation we started with. However applying the inverse of M to A doesn't always result in either  a symmetric or a definite matrix. Hence we brought in transformation where we substitute M with the E.E-Transposed. Such an E can be obtained by say Cholesky Factorization. In this case the substitution helps with making the component symmetric and positive definite. This process of using the CG is called the Transformed Preconditioned Conjugate Gradient Method.  This method has an undesirable characteristic that E must be computed. Instead if we do a few careful variable substitutions, it can eliminate E. If we choose the new residual as E-inverse applied to the original residual and if we choose the new search vector as E-transpose applied to the original search direction, then we can derive what is called the untransformed preconditioned conjugate gradient method.  The derivation works out like this: we start by finding the initial residual based on its definition and a starting position x0. we also set the initial search direction again based on its definition and using the initial residual.  We write down the step length in terms of the above and we write down the next position and the next residual in terms of this step length and their iterative definition. This lets us calculate the factor to use with the iterative defintion for the search vector. The matrix E does not appear in this method.
Since it works for the CG, we can use the same technique to derive a pre-conditioned Steepest Descent Method that does not use E.
Let us take a quick look how.
In the steepest descent method, we use the iterative definition involving the residual and the step-length. We start by finding the intial residual and a starting postion. We write down the step-length in terms of the residual and then we calculate the next position.
The effectiveness of a preconditioner M is determined by the condition number of Minverse A and occassionally by its clustering of eigenvalues. The problem is to find a preconditioner. that approximates A well enough such as to make up for the cost of calculating the  product M-inverse current residual once per iteration. The simplest pre-conditioner is a diagonal matrix. whose diagonal entries are identical to those of A. The process of applying this pre-conditioner, known as diagonal pre-conditioning or Jacobi pre-conditioning, is equivalent to scaling the quadratic form along the coordinate axes.
Another trivial pre-conditioner is to take a matrix M as A which gives us the quadratic form to be perfectly spherical. and so the solution takes only one iteration. The catch is that we aren't solving the linear equation we begin with so this isn't helpful.
There are many other pre-conditioners that have been studied. Some have been much more sophisticated.

#codingexercise
int GetCountOfLinesInSourceCode(string text)
{
         var lines = text.split('\r\n');
         int count = 0;
         bool skip = false;
         foreach ( var line in lines )
         {
              if (String.IsWhiteSpace(line)) continue;
              if (line.startswith(single_line_comment)) continue;
              if (line.startswith(multi_line_comment_begin)) { skip = true; continue;}
              if (line.startswith(multi_line_comment_end)) {skip=false; continue;}
              if (!skip) count++;            
          }
         return count;
}