Gaussian Elimination

This is the RREF technique.

In CS370, we learn to decompose a matrix into 2, i.e. .

The steps are the following:

  1. Factor matrix into , where and are triangular.
  2. Solve for intermediate vector . (forward solve)
  3. Solve for . (backward solve)


Given the factorization , we can rapidly solve . How? This is the same as solving . Rewrite it as . Define , and rewrite this as two separate solves:

  • First: Solve for .
  • Then: Solve for .

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

Because and 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