Complexity of Gauss Elimination vs. Cramer's Rule

 

As a part of my Numerical Methods course, I wrote a short MATLAB script that compares the number of computations required for solving a randomly generated N size matrix by both Gaussian Elimination and by Cramer’s rule.

As per this note on Complexity by P. Danziger:

When we implement an algorithm on a computer, one of the first questions we must ask is how eefficient the algorithm is. By this we mean how many steps it will take in the worst case. This is known as the complexity of the algorithm.

Most references state that that Gauss Elimination is of the third order while Cramer’s rule is of the fourth order.

The note linked above also shows how the number of computations is calculated analytically by literally counting the number of steps involved which shows why Gauss Elimination is $O(n^3)$ while Cramer’s rule is $O(n^4)$.

In this short MATLAB script, I count the number of computations and plot the results.

You can check out the code here:

  1. StepCounter Function
  2. Results and Plots

The first file is a function that accepts the system size (N). So if system size is 4, it will create a randomly generated A matrix and b matrix and solve Ax=b by both Gauss Elimination and Cramer’s Rule. The function also outputs the number of computations performed in each method.

In the second file I am calling the function for different values of N (3, 4, 5, … N) and plotting the number of computations required.

Then in the second file, I also calculate the number of calculations as predicted by the analytical calculations and plot the results from both using code as well as analytical arguments.

This is what the results look like:

You can clearly see that for small-sized systems, Cramer’s rule is faster. Gauss Elimination is faster for higher system size. The crossover happens in case of N=5 for the code linked here.

Also, for some reason (read: un-optimised code), this trend is not seen in the results from code. Nonetheless, the trends do match (or at least that’s what it looks like, doesn’t it?).

Also, on closer examination, I found that the script undercounts the steps in Gauss Elimination and over-counts in the case of Cramer’s rule as seen from the following plot:

Since the objective (for me) was to get a quick understanding of how these two methods compare, correcting the code for higher accuracy is left as an exercise for the reader.

( ͡° ͜ʖ ͡°)

Also, on a side note: have you wondered why Gauss Elimination is called so?