Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Preconditioner
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.