rank() computation cost

Hi, does anyone knows which is the computational cost of getting the rank of a matrix through the rank(M) command? (It would be extremelly usefull to have the order of the command using the Big O notation.

Thank you in advance!

Nicolas

Answer 1

[Shanmukha Voggu]

Hi Nicholas,

The Computational Complexity of the rank function is equal to svd function.

which is equal to O(max(m, n) * min(m, n)^2), where m and n are number of rows and columns of the matrix respectively

Refer this for more information.

[Nicolas Mira Gebauer]

That helped a lot, thanks!

[Christine Tobler]

Hi, I just realized I got that wrong in the Answers post you were referring to: The complexity is actually

O(max(m, n) * min(m, n)^2)

That is, for a square n-by-n matrix the complexity of RANK is cubic in n.

[Shanmukha Voggu]

Thanks for the information, I edited my answer to show up right complexity

[Nicolas Mira Gebauer]

Thank you both for the clarification!

[Walter Roberson]

I was wondering! max(m, n) *min(m, n) as was posted before is the same as m*n, and I couldn't figure out why someone would bother writing it the long way!