An evolutionary algorithm for diagonal scaled preconditioned conjugate gradient

Penney, Peter Martin (2008) An evolutionary algorithm for diagonal scaled preconditioned conjugate gradient. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (57MB)

Abstract

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.

Actions (login required)

View Item