Fast Reduced Row Echelon Form

A much faster version of MATLAB's RREF

Description

For full matrices, the algorithm is based on the vectorization of MATLAB's RREF function. A typical speed-up range is about 2-4 times of the MATLAB's RREF function. However, the actual speed-up depends on the size of A. The speed-up is quite considerable if the number of columns in A is considerably larger than the number of its rows or when A is not dense.

For sparse matrices, the algorithm ignores the tol value and uses sparse QR to compute the rref form, improving the speed by a few orders of magnitude.

Authors: Armin Ataei, Ashish Myles

• Required Products: MATLAB
• MATLAB release: MATLAB 7.14 (R2012a)

[Ashish Myles]

 

[Armin Ataei]

@Angela YANG: Please note that the function frref(A,tol) may compute a slightly different value for the variable "tol" if it ommitted. This is most likely why you got different results when you compared the two. You can try the following code instead:
n = 100;
tol = 1e-6;
A = magic(n);
B = rref(A,tol);
C = frref(A,tol);
error = max(abs(B(:)-C(:)))
-----------------
In my case I got error = 8.4867e-011.
I should also point out that, as you know, A = magic(n) produces a square matrix and therefore A basically corresponds to a linear system of equations with n equations and n-1 variables. It is therefore very likely that such system has no solution at all and its frref does in fact confirm that. Hope this helps.

[Angela YANG]

When I test it for magic matrix, it gave the different answer with matlab.

[Babak]

Very fast and robust. It may not be a bad idea to preallocate 'jb' and then delete the empty elements. Otherwise, awesome!

[Nikola Toljic]

Very good.

[Yi Cao]

It is indead very fast compared to native MATLAB rref. However, I just wonder when the function is most useful.