# Gaussian Elimination

This is the RREF technique.

In CS370, we learn to decompose a matrix into 2, i.e. $A=LU$.

The steps are the following:

- Factor matrix $A$ into $A=LU$, where $L$ and $U$ are triangular.
- Solve $Lz=b$ for intermediate vector $z$. (forward solve)
- Solve $Ux=z$ for $x$. (backward solve)

### Motivation

Given the factorization $A=LU$, we can rapidly solve $Ax=b$. How? This is the same as solving $LUx=b$. Rewrite it as $L(Ux)=b$. Define $z=Ux$, and rewrite this as two separate solves:

- First: Solve $Lz=b$ for $z$.
- Then: Solve $Ux=z$ for $x$.

Why are two solves better than one (i.e., our original system)?

Because $L$ and $U$ are both triangular: all entries above, or below, the diagonal are zero, respectively. This makes them easier (i.e., more eācient) to solve.

### Time Complexity of the Algorithm

We saw this in CS370.

- Factorization is the dominant term