What is the complexity of Matlab's implementation of SVD?

According to Matrix Computations textbook, it should be something ~ O(m^2n) which is pretty much what I get for matrices where m,n >=10,000 but for smaller matrices say up to 1000x000 I find that ~O(m^2).

Answer 1

[Christine Tobler]

The computational complexity of svd is O(max(m, n) * min(m, n)^2). If the 'econ' flag is not used and all three matrices are returned, at least a complexity of O(max(m, n)^2) needs to be added for constructing the larger of the two orthogonal matrices that are returned.

[Haochuan Song]

Could you suggest the algorithm that used to calculate SVD with 'econ' in matlab?

[Christine Tobler]

The algorithm used is the same for both 'econ' and non-'econ' versions, only the post-processing changes. I can't give the exact algorithm used, but I would suggest looking at the LAPACK documentation or at "Matrix Computations" by Golub and Van Loan for a general description of the basis behind the algorithm used to compute the SVD and many other linear algebra operations.

[Christine Tobler]

Edited the original answer with a correction: It should have said

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

when it previously was saying

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

[Zefan Lin]

Hi~What is the difference in the time complexity required for MATLAB to implement real SVD and complex SVD?

[Christine Tobler]

The complexity is the same between real and complex SVD (in terms of actual run-time, complex SVD should be expected to be slower. On average, complex computations are usually about a factor 4 more expensive (because of the cost of multiplying two complex numbers), but this is a rough estimate. The actual difference in execution time will likely change based on many factors such as the machine used, the MATLAB version, the number of threads and more.

[Zefan Lin]

OK, I understand, thank you~

[Zefan Lin]

Hello! I am still a bit confused about the statement "The complexity is the same between real and complex SVD." Multiplying two real numbers only requires one multiplication operation, while multiplying two complex numbers requires four multiplication operations and three addition operations. So why is the computation complexity of real SVD the same as that of complex SVD? Could you please help me clarify this? Thank you!

[Christine Tobler]

The computational complexity doesn't refer to the number of operations, instead it's only about the speed at which the number of operations grows as the problem size grows.

So if we have two functions, one of which takes 2*N operations for a vector of length N, and another takes 10*N operations for the same vector, we would say both have computational complexity O(N). This means that if you double N, in both cases this will double the number of operations.

[Bowen]

How can I cite it in a paper? is it a reference?