LU Decomposition Algorithm

LU decomposition factors a square matrix into the product of a lower triangular matrix L and an upper triangular matrix U, typically computed as a byproduct of running Gaussian elimination and recording the multipliers used at each elimination step into L while the resulting eliminated matrix becomes U. Once a matrix is factored this way, solving a linear system against it, or against several different right-hand sides, becomes much cheaper than repeating full Gaussian elimination each time, since forward and back substitution against triangular matrices are fast. The technique is named for the lower and upper triangular matrices it produces and is a standard building block of numerical linear algebra software.