Linear solver Created 2026-10-25 Updated 2026-11-05
A linear solver is an algorithm that computes a solution or controlled approximation to a linear system . For an invertible matrix, the mathematical solution is unique. A direct linear solver usually computes a matrix factorization, such as Pivoted LU decomposition, followed by triangular solves. An iterative method instead updates an approximate vector, often using matrix-vector products and a matrix preconditioner.
A stopping rule should reflect the required accuracy. The linear-system residual can be scaled as
when the denominator is positive, using compatible vector norms and an induced matrix norm. This compares equation error with the input scale; a condition number is still needed to interpret it as a forward error guarantee. In a differential equation computation, the linear solver tolerance must be small enough relative to the intended discretization accuracy. A stable time step alone does not control errors left by an inaccurate inner solve.
Matrix preconditioner Created 2026-10-06 Updated 2026-10-18
A matrix preconditioner is an auxiliary invertible matrix whose matrix inverse is cheap to apply and whose use improves the eigenvalues of a linear system. In symmetric positive-definite matrix problems, a symmetric positive-definite matrix preserves that structure under the symmetric transformation .
Applying means solving for a supplied vector . This notation does not require forming a general matrix inverse. A diagonal matrix gives componentwise divisions; a factored matrix gives auxiliary solves such as forward substitution and back substitution.[ref]
Choosing makes the solve trivial but changes nothing; choosing gives the exact correction but asks us to solve the original linear system.[ref]
Matrix preconditioning Created 2026-10-06 Updated 2026-10-31
Matrix preconditioning transforms a linear system using an inexpensive auxiliary solve to improve its eigenvalues. For symmetric positive-definite matrices, a symmetric positive-definite matrix produces , preserving the symmetric structure needed by the conjugate gradient method.
A useful matrix preconditioner combines a cheap solve with favorable transformed eigenvalues; neither property alone is enough.[ref]
The aim is to make each correction more effective without making it expensive. The example under diagonal scaling for a two-dimensional linear system turns thin ellipses into nearly circular ones and makes preconditioned steepest descent effective.
The linear-system residual at an approximate solution is . For symmetric positive definite , the conjugate gradient method has and minimizes the squared -norm of the error over that affine space; its residual is orthogonal to .
If has distinct eigenvalues, interpolate on them with a polynomial of degree at most . The finite-dimensional spectral theorem gives , so the exact correction lies in . The minimum possible error at step is therefore zero. Thus in exact arithmetic, possibly earlier if the initial residual has fewer eigencomponents. If , it terminates immediately.
A symmetric positive definite matrix preconditioner changes the system to , with ; practical preconditioned CG applies solves with . It can accelerate convergence by reducing the spectral condition number of a positive-definite matrix, which improves the usual bound involving , and by clustering eigenvalues, which allows low-degree residual polynomials small on the spectrum even when the extreme-eigenvalue bound is pessimistic.
Choosing makes the transformed matrix , so one step suffices. But applying already requires solving the original problem, and constructing an exact factorization generally incurs its original computational cost. It is therefore not a useful shortcut for a single unsolved system, though an available factorization can be reused for multiple right-hand sides. Effective matrix preconditioning balances spectral improvement against inexpensive application.