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. Preconditioning for linear systems. In linear algebra and numerical analysis, a preconditioner formula_1 of a matrix formula_2 is a matrix such that formula_3 has a smaller condition number than formula_2. It is also common to call formula_5 the preconditioner, rather than formula_1, since formula_1 itself is rarely explicitly  available. In modern preconditioning, the application of formula_5, i.e., multiplication of a column vector, or a block of column vectors, by formula_5, is commonly performed in a matrix-free fashion, i.e., where neither formula_1, nor formula_5 (and often not even formula_2) are explicitly available in a matrix form. Preconditioners are useful in iterative methods to solve a linear system formula_13 for formula_14 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 formula_2 is not stored explicitly, but is accessed by evaluating matrix-vector products. Description. Instead of solving the original linear system above, one may consider the right preconditioned system and solve for formula_18 and for formula_14. Alternatively, one may solve the left preconditioned system Both systems give the same solution as the original system as long as the preconditioner matrix formula_1 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 formula_2 is real symmetric and real preconditioners formula_25 and formula_1 satisfy formula_27 then the preconditioned matrix formula_28 is also symmetric. The two-sided preconditioning is common for diagonal scaling where the preconditioners formula_25 and formula_1 are diagonal and scaling is applied both to columns and rows of the original matrix formula_2, e.g., in order to decrease the dynamic range of entries of the matrix. The goal of preconditioning is reducing the condition number, e.g., of the left or right preconditioned system matrix formula_32 or formula_33. Small condition numbers benefit fast convergence of iterative  solvers and improve stability of the solution with respect to perturbations in the system matrix and the right-hand side, e.g., allowing for more aggressive quantization of the matrix entries using lower computer precision. The preconditioned matrix formula_32 or formula_33 is rarely explicitly formed. Only the action of applying the preconditioner solve operation formula_36 to a given vector may need to be computed. Typically there is a trade-off in the choice of formula_1. Since the operator formula_36 must be applied at each step of the iterative linear solver, it should have a small cost (computing time) of applying the  formula_36 operation. The cheapest preconditioner would therefore be formula_40 since then formula_41 Clearly, this results in the original linear system and the preconditioner does nothing. At the other extreme, the choice formula_42 gives formula_43 which has optimal condition number of 1, requiring a single iteration for convergence; however in this case formula_44 and applying the preconditioner is as difficult as solving the original system. One therefore chooses formula_1 as somewhere between these two extremes, in an attempt to achieve a minimal number of linear iterations while keeping the operator formula_36 as simple as possible. Some examples of typical preconditioning approaches  are detailed below. Preconditioned iterative methods. Preconditioned iterative methods for formula_47 are, in most cases, mathematically equivalent to standard iterative methods applied to the preconditioned system formula_48 For example, the standard Richardson iteration for solving formula_47 is Applied to the preconditioned system formula_51 it turns into a preconditioned method Examples of popular preconditioned iterative methods for linear systems include the preconditioned conjugate gradient method, the biconjugate gradient method, and generalized minimal residual method. Iterative methods, which use scalar products to compute the iterative parameters, require corresponding changes in the scalar product together with substituting formula_53 for formula_54 Matrix splitting. A  stationary iterative method is determined by the matrix splitting formula_55 and the iteration matrix formula_56. Assuming that the condition number formula_60 is bounded above by Geometric interpretation. For a symmetric positive definite matrix formula_2 the preconditioner formula_1 is typically chosen to be symmetric positive definite as well. The preconditioned operator formula_32 is then also symmetric positive definite, but with respect to the formula_1-based scalar product. In this case, the desired effect in applying a preconditioner is to make the quadratic form of the preconditioned operator formula_32 with respect to the formula_1-based scalar product to be nearly spherical. Variable  and non-linear preconditioning. Denoting formula_5, we highlight that preconditioning is practically implemented as multiplying some vector formula_69 by formula_70, i.e., computing the product formula_71 In many applications, formula_70 is not given as a matrix, but rather as an operator formula_73 acting on the vector formula_69. Some popular preconditioners, however, change with formula_69 and the dependence on formula_69 may not be linear. Typical examples involve using non-linear iterative methods, e.g., the conjugate gradient method, as a part of the preconditioner construction. Such preconditioners may be practically very efficient, however, their behavior is hard to predict theoretically. Random preconditioning. One  interesting particular case of variable preconditioning is random preconditioning, e.g., multigrid preconditioning on random course grids. If used in gradient descent methods, random preconditioning can be viewed as an implementation of stochastic gradient descent and can lead to faster convergence, compared to fixed preconditioning, since it breaks the asymptotic "zig-zag" pattern of the gradient descent. Spectrally equivalent preconditioning. The most common use of preconditioning is for iterative solution of linear systems resulting from approximations of partial differential equations. The better the approximation quality, the larger the matrix size is. In such a case, the goal of optimal preconditioning is , on the one side, to make the spectral condition number of formula_3 to be bounded from above by a constant independent of the matrix size, which is called "spectrally equivalent" preconditioning by D'yakonov. On the other hand, the cost of application of the formula_78 should ideally be proportional (also independent of the matrix size) to the cost of multiplication of formula_2 by a vector. Examples. Jacobi (or diagonal) preconditioner. The Jacobi preconditioner is one of the simplest forms of preconditioning, in which the preconditioner is chosen to be the diagonal of the matrix formula_80 Assuming formula_81, we get formula_82 It  is efficient for diagonally dominant matrices formula_83. It is used in analysis softwares for beam problems or 1-D problems (EX:- STAAD PRO) SPAI. The Sparse Approximate Inverse preconditioner minimises formula_84 where formula_85 is the Frobenius norm and formula_86 is from some suitably constrained set of sparse matrices. Under the Frobenius norm, this reduces to solving numerous independent least-squares problems (one for every column). The entries in formula_70 must be restricted to some sparsity pattern or the problem remains as difficult and time-consuming as finding the exact inverse of formula_2. The method was introduced by M.J. Grote and  T. Huckle together with an approach to selecting sparsity patterns. Preconditioning for eigenvalue problems. Eigenvalue problems can be framed in several alternative ways, each leading to its own preconditioning. The traditional preconditioning is based on the so-called "spectral transformations." Knowing (approximately) the targeted eigenvalue, one can compute the corresponding eigenvector by solving the related homogeneous linear system, thus allowing to use preconditioning for linear system. Finally, formulating the eigenvalue problem as optimization of the Rayleigh quotient brings preconditioned optimization techniques to the scene. Spectral transformations. By analogy with linear systems, for an eigenvalue problem formula_89 one may be tempted  to replace the matrix formula_2 with the matrix formula_32 using a preconditioner formula_1. However, this makes sense only if the seeking eigenvectors of formula_2 and formula_32 are the same. This is the case for spectral transformations. The most popular spectral transformation is the so-called "shift-and-invert" transformation, where for a given scalar formula_95, called the "shift", the original eigenvalue problem formula_89 is replaced with the shift-and-invert problem formula_97. The eigenvectors are preserved, and one can solve the shift-and-invert problem by an iterative solver, e.g., the power iteration. This gives the Inverse iteration, which normally  converges to the eigenvector, corresponding to the eigenvalue closest to the shift formula_95. The Rayleigh quotient iteration is a shift-and-invert method with a variable shift. Spectral transformations are specific for eigenvalue problems and have no analogs for linear systems. They require accurate numerical calculation of the transformation involved, which becomes the main bottleneck for large problems. General preconditioning. To make a close connection to linear systems, let us suppose that the targeted eigenvalue formula_99 is known (approximately). Then one can compute the corresponding eigenvector from the homogeneous linear system formula_100. Using the concept of left preconditioning for linear  systems, we obtain formula_101, where formula_70 is the preconditioner, which we can try to solve using the Richardson iteration The "ideal" preconditioning. The Moore–Penrose pseudoinverse formula_104 is the preconditioner, which makes the Richardson iteration above converge in one step with formula_105, since formula_106, denoted by formula_107, is the orthogonal projector on the eigenspace, corresponding to formula_99. The choice formula_104 is impractical for three independent reasons. First, formula_99 is actually not known, although it can be replaced with its approximation formula_111. Second, the exact Moore–Penrose pseudoinverse requires the knowledge of the eigenvector, which we are trying to find. This  can be somewhat circumvented by the use of the Jacobi–Davidson preconditioner formula_112, where formula_113 approximates formula_107. Last, but not least, this approach requires accurate numerical solution of linear system with the system matrix formula_115, which becomes as expensive for large problems as the shift-and-invert method above. If the solution is not accurate enough, step two may be redundant. Practical preconditioning. Let us first replace the theoretical value formula_99 in the Richardson iteration above with its current approximation formula_117 to obtain a practical algorithm A popular choice is formula_119 using the Rayleigh quotient function formula_120. Practical preconditioning may  be as trivial as just using formula_121 or formula_122 For some classes of eigenvalue problems the efficiency of formula_123 has been demonstrated, both numerically and theoretically. The choice formula_123 allows one to easily utilize for eigenvalue problems the vast variety of preconditioners developed for linear systems. Due to the changing value formula_117, a comprehensive theoretical convergence analysis is much more difficult, compared to the linear systems case, even for the simplest methods, such as the Richardson iteration. Preconditioning in optimization. In optimization, preconditioning is typically used to accelerate first-order optimization algorithms. Description. For example, to find a local minimum  of a real-valued function formula_126 using gradient descent, one takes steps proportional to the "negative" of the gradient formula_127 (or of the approximate gradient) of the function at the current point: The preconditioner is applied to the gradient: Preconditioning here can be viewed as changing the geometry of the vector space with the goal to make the level sets look like circles. In this case the preconditioned gradient aims closer to the point of the extrema as on the figure, which speeds up the convergence. Connection to linear systems. The minimum of a quadratic function where formula_131 and formula_132  are real column-vectors and formula_2 is a real symmetric positive-definite matrix, is exactly the solution of the linear equation formula_134. Since formula_135, the preconditioned gradient descent method of minimizing formula_126 is This is the preconditioned Richardson iteration for solving a system of linear equations. Connection to eigenvalue problems. The minimum of the Rayleigh quotient where formula_131 is a real non-zero column-vector and formula_2 is a real symmetric positive-definite matrix, is the smallest eigenvalue of formula_2, while the minimizer is the corresponding eigenvector. Since formula_142 is proportional to formula_143, the preconditioned gradient descent method of minimizing  formula_144 is This is an analog of preconditioned Richardson iteration for solving eigenvalue problems. Variable preconditioning. In many cases, it may be beneficial to change the preconditioner at some or even every step of an iterative algorithm in order to accommodate for a changing shape of the level sets, as in One should have in mind, however, that constructing an efficient preconditioner is very often computationally expensive. The increased cost of updating the preconditioner can easily override the positive effect of faster convergence.