An evolutionary algorithm for diagonal scaled preconditioned conjugate gradient
Peter Martin Penney · Memorial University Research Repository (Memorial University) · 2008
The Preconditioned Conjugate Gradient method (PCG) is an iterative method used to solve linear systems of equations Ax=b, were A is often a large and sparse matrix. In the PCG method, diagonal scaling (Jacobi scaling) may be used to precondition the Matrix A so that the method converges in fewer iteration steps than the conventional conjugate gradient method. Diagonal scaling is carried out by using the diagonal of A as a preconditioner at each conjugate gradient iteration step. This project proposes a novel approach using an evolutionary algorithm to evolve different diagonal matrices to precondition the Matrix A at each iteration step. The evolutionary algorithm proceeds by applying computational crossover and mutation operators to generate a small population of matrices. The diagonal matrix resulting in the lowest relative residual in the population (higher fitness) is selected to pre-condition the Matrix A for the next iteration. Subsequently, a new generation of diagonal matrices will compete to become the preconditioner for the following iteration. This process continues for the number of iteration steps defined by the PCG Method. Results from conventional diagonal scaled PCG method will be compared with the evolutionary algorithm based diagonal scaled PCG method.