Left preconditioning: Why do we multiply with $P^{-1}$ and not with $P$?

Question

In the numerical analysis class we learnt about preconditioning. What the professor explained is the following:

If in the problem $Ax=b$ that we want to solve the matrix $A$ is ill-conditioned (so $\kappa (A)$ is "large"), we try to find the matrix $P$ (symmetrical and positive definite), such that $\kappa(PA)<\kappa(A)$ and we solve $PAx=Pb$ instead.

After looking at the Wikipedia page about this problem I found out that what the professor explained was left preconditioning. My question is: On the Wikipedia page, they seem to multiply with $P^{-1}$ instead of $P$. Why? Does this make any difference?

Answer 1

A good preconditioner for $Ax=b$ is a nonsingular matrix $M$ such that $M^{-1}$ is a good approximation of $A^{-1}$ and such that systems of the form $My=c$ can be solved rapidly on the available hardware. Instead of solving $Ax=b$ we solve the equivalent system $M^{-1}Ax=M^{-1}b$.

In order to apply a variety of iterative methods we do not need to explicitly compute the matrix $M^{-1} A$. These methods often hinge on our ability to compute matrix vector products of the form $q=M^{-1} A z$. This can be done by first computing the product $p=Az$ and then solving the linear system $Mq = p$ with respect to $q$. Finally, many iterative methods converge rapidly when the effective matrix, i.e., $M^{-1}A$ is close to the identity matrix. This is precisely why we require that $M^{-1}$ is a good approximation of $A^{-1}$, so that $M^{-1}A$ is very nearly the identity matrix.

In the context of numerical linear algebra, the notation $PAx=Pb$ is frequently used to emphasize that $P$ is permutation matrix and that we are dealing with Gaussian elimination with partial pivoting. On the other hand, the notation $M^{-1}Ax = M^{-1}b$ is frequently used to indicate that we are dealing with left-preconditioning and emphasize that $M$ is nonsingular.