How is SVDS execution time related to the target rank?

3 次查看(过去 30 天)
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 个评论
KSSV
KSSV 2021-8-23
编辑:KSSV 2021-8-23
Behaviour is the same but the time taken reduces that's it.
Francesco Di Mauro
Francesco Di Mauro 2021-8-23
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.

请先登录,再进行评论。

采纳的回答

Christine Tobler
Christine Tobler 2021-8-23
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 个评论
Christine Tobler
Christine Tobler 2021-8-23
With a dense matrix of size 400-by-1024, I'd expect that you're going to be faster just calling svd(A) directly for nearly any target rank. Usually large (think >1e4) sparse matrices are the best places to apply svds.
You might try out the new svdsketch, which has some chance of having better performance (though keep in mind this doesn't necessarily compute the largest singular value - it computes the best rank-1 approximation to A up to a tolerance).
Francesco Di Mauro
Francesco Di Mauro 2021-8-23
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!

请先登录,再进行评论。

更多回答(0 个)

类别

Help CenterFile Exchange 中查找有关 Mathematics and Optimization 的更多信息

标签

产品


版本

R2017b

Community Treasure Hunt

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

Start Hunting!

Translated by