How is SVDS execution time related to the target rank?

5 views (last 30 days)
I assumed that the higher the target rank, the longer the running time of the SVDS function would be, but I was getting weird results, so I tried this small test function:
C = rand(400,1024); % random matrix, actual rank = 400
ranks = [5:5:200 250 400];
n = numel(ranks);
running_times = zeros(n,1);
for r = 1:n
for j = 1:10 % average running time for current rank over 10 runs
t = tic;
svds(C, ranks(r));
running_times(r) = running_times(r) + toc(t);
end
running_times(r) = running_times(r)/10;
end
plot(running_times, 'marker', 'o');
set(gca, 'XTick', 1:n, 'XTickLabel', ranks);
xlabel('target rank');
ylabel('seconds');
set(gcf, 'position', [346 346 1334 338]);
set(findall(gca, 'Type', 'Line'), 'LineWidth', 2);
xlim([1 n]);
ylim([0 0.55]);
grid on;
and this are the results I get:
Do you guys know what may cause the huge drop between ranks 130 and 135? And why rank 130 is so much slower than 400 (full rank)?
Thanks!
  4 Comments
Francesco Di Mauro
Francesco Di Mauro on 23 Aug 2021
Sorry, by "function" I meant my script, not the SVDS function, what I was trying to say is that I get the same running times either with my way of collecting them or yours.

Sign in to comment.

Accepted Answer

Christine Tobler
Christine Tobler on 23 Aug 2021
So the goal of svds is usually to compute a requested rank that is much smaller than either size of the input matrix. A search space is constructed which has (by default) about 3 times as many vectors in it as the requested rank.
If that search space ends up being larger than the size of the original matrix A (that is, if 3*k >= min(size(A)) ), svds will fall back on just computing svd(full(A)), as this will definitely be faster in that case. But even before that, svds is only advisable to be used if the number of singular values requested is significantly smaller than the size of A - as is shown in your plot.
For the smaller jump seen at target rank 105-110, that's probably a bit of luck based on the specific matrix: As the target rank increases, the search space size increases, and it's possible that a larger search space will need fewer iterations to find all singular values requested. This is a bit of balancing between parameters, it's normal for the timings here to not just steadily increase.
  2 Comments
Francesco Di Mauro
Francesco Di Mauro on 23 Aug 2021
Thank you very much, I was under the wrong assumption that svds would always be faster than svd, now it is more clear to me how they work!

Sign in to comment.

More Answers (0)

Tags

Products


Release

R2017b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by