Algorithms
The LU decomposition is basically a modified form of Gaussian elimination. We transform the matrix A into an upper triangular matrix U by eliminating the entries below the main diagonal. The Doolittle algorithm does the elimination column by column starting from the left, by multiplying A to the left with atomic lower triangular matrices. It results in a unit lower triangular matrix and an upper triangular matrix. The Crout algorithm is slightly different and constructs a lower triangular matrix and a unit upper triangular matrix.
Computing the LU decomposition using either of these algorithms requires 2n3 / 3 floating point operations, ignoring lower order terms. Partial pivoting adds only a quadratic term; this is not the case for full pivoting.
Read more about this topic: LU Decomposition