How is SVDS execution time related to the target rank?
1 次查看(过去 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:
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/718504/image.png)
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 个评论
采纳的回答
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
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).
更多回答(0 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Mathematics and Optimization 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!