LU factorization

factorizing by where is lower triangular and is upper triangular matrix.

Basic factorization method

Make all diagonal elements of to one and manually calculate it with .

3x3 example

So we can say

Multiplying factorization method (like Gaussian elimination?)

Started with where is identical matrix.

3x3 example

then eliminate term by first or second row etc.

Partial Pivot

Exchange rows to let the biggest element in first row.
Given by the formula .
But there are types that no need to pivot at all:

• Diagonally dominant
• SPD, where we can use Cholesky factorization instead

Applications

After factorization, we can solve by Forward-backward substitution.
Basically is equivalent to .

Sherman-Morrison

We can solve those and by Forward-backward substitution.

Costs

generally total cost in operations
But after enable partial pivoting (only row exchange), total cost is
However for full pivoting, it is still for additional searching cost

Code

credit: UTexas.

import numpy as np
 
def LU(A):
	n = A.shape[0]
	U = A.copy()
	L = np.eye(n, dtype=np.double)
	for i in range(n):
		factor = U[i + 1:, i] / U[i, i]
		L[i + 1:, i] = factor
		U[i + 1:] -= factor[:, np.newaxis] * U[i]
	return L, U