Preconditioner

In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducing a condition number of the problem. The preconditioned problem is then usually solved by an iterative method. In linear algebra and numerical analysis, a preconditioner of a matrix is a matrix such that has a smaller condition number than . It is also common to call the preconditioner, rather than , since itself is rarely explicitly available. In modern preconditioning, the application of , i.e., multiplication of a column vector, or a block of column vectors, by , is commonly performed in a matrix-free fashion, i.e., where neither , nor (and often not even ) are explicitly available in a matrix form. Preconditioners are useful in iterative methods to solve a linear system for since the rate of convergence for most iterative linear solvers increases because the condition number of a matrix decreases as a result of preconditioning. Preconditioned iterative solvers typically outperform direct solvers, e.g., Gaussian elimination, for large, especially for sparse, matrices. Iterative solvers can be used as matrix-free methods, i.e. become the only choice if the coefficient matrix is not stored explicitly, but is accessed by evaluating matrix-vector products. Instead of solving the original linear system for , one may consider the right preconditioned system and solve for and for . Alternatively, one may solve the left preconditioned system Both systems give the same solution as the original system as long as the preconditioner matrix is nonsingular. The left preconditioning is more traditional. The two-sided preconditioned system may be beneficial, e.g., to preserve the matrix symmetry: if the original matrix is real symmetric and real preconditioners and satisfy then the preconditioned matrix is also symmetric.