Gaussian elimination is direct method of solving systems of linear equations. Recall that a system of linear equations can be expressed as a simple equation Ax = b, where A is an nxn square matrix, and the given b, and the unknown x are both vectors of size n (nx1 matrices).

Gaussian elimination works by turning to zero (eliminating) every element in the ith column below the ith row of A. The elimination step is done by adding a multiple of the ith row of A to the i+kth row of A.

If A is an nxn matrix, the time complexity of Gaussian elimination is O(n^{3}). This makes it an impractical algorithm for a lot of scientific applications, where the matrix may be sparse (ie composed mostly of zeroes), but n can be in the order of millions.

A potentially cheaper way of solving systems of linear equations is using the so called "iterative methods."