Preconditioning |

Iterative methods (like conjugate-directions) can sometimes be accelerated by a change of variables. The simplest change of variable is called a ``trial solution.'' Formally, we write the solution as:

(3) |

where is the map we seek, columns of the matrix are ``shapes'' we like and coefficients in are unknown coefficients to select amounts of the favored shapes. The variables are often called the ``preconditioned variables.'' It is not necessary that be an invertible matrix, but we see later that invert-ability is helpful. Inserting the trial solution into gives:

(4) | |||

(5) |

We pass the operator to our iterative solver. After finding the best fitting , we merely evaluate to get the solution to the original problem.

We hope this change of variables has saved effort. For each iteration, there is a little more work: Instead of the iterative application of and , we have iterative application of and .

Our hope is that the number of iterations decreases, because we are clever or because we have been lucky in our choice of . Hopefully, the extra work of the preconditioner operator is not large compared to . If we should be so lucky that , then we get the solution immediately. Obviously we would try any guess with . Where I have known such matrices, I have often found that convergence is accelerated, but not by much. Sometimes, it is worth using for a while in the beginning; but later, it is cheaper and faster to use only . A practitioner might regard the guess of as prior information, like the guess of the initial model .

For a square matrix , the use of a preconditioner should not change the ultimate solution. Taking to be a tall rectangular matrix reduces the number of adjustable parameters, changes the solution, gets it quicker, but lowers resolution.

Preconditioning |

2015-05-07