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:

1. Factor matrix $A$ into $A=LU$, where $L$ and $U$ are triangular.
2. Solve $Lz=b$ for intermediate vector $z$. (forward solve)
3. 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