Mathematics
The LU decomposition is one of the most basic tenets of
numerical linear algebra. It is used to solve the linear system of equations Ax=b
While it is possible to solve this system by using an explicit
inverse of A, i.e. x = A
-1b, this is almost never a good idea for efficiency reasons. A numerical analyst would never do that. Instead, a factorization of A is more effective. One standard factorization is to factorize A=LU where L is a
lower triangular matrix and U is an
upper triangular matrix. Then Ax=b may be solved as follows:
Ax = b
(LU)x = b
L(Ux) = b
now let c denote Ux and solve the system
Lc = b
Single L is lower triangular, this is a simple forward substitution. Once we know c we then solve
Ux = c
via backward substitution and we are done. This method has the advantage that multiple right hand side solves can be done quite quickly.
Other important decompositions include the
Choleski Decomposition and the
QR Decomposition.