What is the computational cost of reduced row echelon and finding the null space?

Question

I'm taking computational linear algebra, and haven't been able to find too much information about the computational cost (in terms of m=rows and n=cols) of these two routines:

Reduced Row Echelon Form on a Matrix A

Finding the null space of Matrix A

Any help would be great!

Thanks!

Answer 1

Usually one does not fine the exact null space of a matrix A. I don't know of an algorithm that actually computes the reduced row echelon form of a matrix.

Rather, there is something like an "approximate" null space to a matrix. The approximate null space I'm talking about is the set of singular vectors corresponding to small singular values.

The computational cost of finding the approximate null space depends on how stable you want your method to be. Three commonly used techniques are LU decomposition, QR decomposition, and Singular Value Decomposition (SVD). LU decomposition is the fastest method, but it's the most unstable. Then QR decomposition. SVD is the most stable but the slowest method.