Preconditioning

Preconditioning is a technique (not peculiar to just the CG method) consisting in preconditioning the system that we want to solve, so that the new system has better properties (e.g. faster convergence to the solution of numerical methods, less cost of computation,...). The solution to the original problem can be easily contructed from the solution of the preconditioned problem. Usually the main aim of preconditioning is to reduce the condition number of the problem.

Contents

Theory

Instead of solving the system $Ax = b$, we precondition the system and try to solve the system

$P^{\top}AP\tilde{x} = P^{\top}b$ if we want to use split preconditioning, where $x = P\tilde{x}$,

or

$P^{\top}Ax = P^{\top}b$ if we want to use left preconditioning.

Since we want to apply the CG method, we need to make sure that $P^{\top}AP$ (if we use split preconditioning) or $P^{\top}A$ (if we use left preconditioning) is SPD.

We can then apply the CG method to the preconditioned system. In the case of split preconditioning, the preconditioned solution is related to the original solution by $x_{orig} = P x_{prec}$, while for the left preconditioning the solutions of the original and of the preconditioned systems coincide.

The GUI

Running the downloadable MATLAB® code on this page opens a GUI which allows you to play with preconditioning.

precond_GUI

Interface

You can input the matrix $A$ and the column vector $b$ of the system $Ax = b$, and can also decide whether you want to input the preconditioner $P$ manually, or choose between some preset preconditioners (option available only if you are using split conditioning). You can also set the tolerance, which determines the degree of precision of the numerical method in finding the solution.

If you decide to use the split conditioning, you just need to make sure that the input square matrix $A$ is SPD. A quick way to generate such an $A$ is to do:

$M$ = any non-singular matrix

A = $M^{\top}M$.

For $P$, you can then input any non-singular square matrix of the same dimensions of $A$. The conditioned matrix $P^{\top} A P$ will still be SPD.

If you decide to use left conditioning, things are trickier since you need to make sure that the preconditioner $P$ is such that $P^{\top}A$ is SPD, otherwise the method will not converge.

When you input $A$ or $P$, the condition numbers $\kappa(A)$ and $\kappa(P^{\top}AP)$ (split) or $\kappa(P^{\top}A)$ (left) will appear automatically. Play with $P$ to see how the condition numbers change.

When you have input all the relevant stuff, click on 'Show' to display the number of iterations for both the original and the preconditioned system, the eigenvalues of $A$ and $P^{\top}AP$ (split) or $P^{\top}A$ ( left), and a bar chart displaying the spectrum of $A$ in green, and the spectrum of the preconditioned matrix in blue (so that you can see how preconditioning redistributes the spectrum, and hence changes the condition number).

Code

All files as .zip archive: precond_all.zip

Published with MATLAB® R2017a