Computing SVD very slow

[filipekstrm]

Hi. Very interesting work!

I have started exploring the codebase, and found that computing the SVD in the linear inverse scattering problem is very slow, and when trying it took way longer than the 10-20 minutes that the comment indicates (in fact, I let it compute for some 90 minutes before giving up)

However, I found that instead of torch.svd(A) using U, Sigma, Vt = torch.linalg.svd(A, full_matrices=False, driver="gesvd") reduced the time to a mere ~4 minutes (where the use of the driver argument seems to have made the difference). Additionally, I used these results to compute the pseudoinverse instead of torch.linalg.pinv(A). This means the computation of the pseudoinverse takes essentially 0s.

So, first question: did you use torch.svd(A) when computing the SVD initially, and would using my solution above with torch.linalg.svd(A, full_matrices=False, driver="gesvd") be ok?

Second question: is it necessary to use torch.linalg.pinv(A)?

Of course, these computations are only done once, but as the print said that it would take 10-20 minutes and mine wasn't done after 90 minutes, I got curious and thought about how to make it faster.

[devzhk]

Hi,

thanks for digging in and sharing your findings.

1. Yes, we originally used torch.svd(A). I can confirm that it took us less than 30 minutes on a single A100 (you may check if the SVD is accelerated by cuda). Using torch.linalg.svd with driver="gesvd" is perfectly OK.
2. Caveat about reduced SVD: this might cause shape mismatch for some algorithms like DDRM and FPS which expect U, V to be square matrix.
3. You're right. torch.linalg.pinv(A) is not necessary when we have the SVD.

Your change should be fine for most algorithms in the repo except for DDRM and FPS.

BTW, I also put the SVD results here so that you don't need to compute it locally.

[filipekstrm]

Hm, I used full_matrices=False as this is, according to pytorch docs, equivalent to the default arguments of torch.svd. Using FPS with these reduced matrices at least runs and does not give give any errors