[StevenB]

Originally Posted by Michael Hill

Wouldn't it me much less computationally intensive to actually solve the matrix into reduced row echelon form?

Interestingly, no. Gaussian elimination is O(N^3), which gets ugly really fast. When you get into the realm of hundreds or thousands of elements, there are much better ways to do it, which computational packages like MATLAB take full advantage of. I've attached a graph showing the computation times for Gaussian elimination, invert-and-multiply, and direct solve for a variety of matrix sizes. By the time you get to 300 elements, Gaussian elimination is already painfully slow, but even the invert-and-multiply has hardly broken a sweat (less than 0.02 seconds).

This test was run on my 6-year-old Core 2 Duo (T7200 @ 2.00GHz) laptop with MATLAB R2010a. Sometime later this week I'll see about running the matrix solve on a real computer, maybe one with a little extra horsepower.

sizes = floor(logspace(1, 2.5, 10));
times = zeros(length(sizes), 3);

for s = 1:length(sizes);
  A = rand(sizes(s));
  b = rand(sizes(s), 1);
  
  %% Gaussian elimination
  tic;
  nIters = 1;
  for ii = 1:nIters;
    r = rref([A b]);
    x = r(:, end);
  end
  times(s, 1) = toc / nIters;
  
  %% Invert and multiply
  tic;
  nIters = 50;
  for ii = 1:nIters;
    x2 = inv(A) * b;
  end
  times(s, 2) = toc / nIters;
  
  %% Direct solve in MATLAB
  tic;
  nIters = 50;
  for ii = 1:nIters;
    x3 = A \ b;
  end
  times(s, 3) = toc / nIters;

end

plot(sizes, times, '-x');
xlabel('Matrix size');
ylabel('Computation time [s]');
legend('Gaussian elimination (rref)', 'Invert and multiply', 'Direct solve')

EDIT: It's been pointed out to me that a matrix inversion is also inherently O(n^3), and so there's something else at work making it slow. In this case, the catch is that rref() is written in plain MATLAB code (try "edit rref"), while inversion and solving are implemented as highly-optimized C code. Gaussian elimination is not the fastest, but it's not nearly as bad as I made it out to be.

Thanks to those who pointed this out. Obviously I need to go study some more linear algebra. That's on the schedule for the fall.