How is SVDS execution time related to the target rank?

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!

[KSSV]

I think a small change in calculating the time taken.

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    
    rt = 0 ; 
	for j = 1:10	% average running time for current rank over 10 runs
		t1 = tic;
		svds(C, ranks(r));
        t2 = toc(t1) ; 
		rt = rt+t2;
	end
	running_times(r) = rt/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;

[Francesco Di Mauro]

Thanks for the answer! Your code is indeed more readable, but it does not seem to change the behaviour of the function, I get the same exact results, unless I'm doing something else wrong... Do you have a chance to run it yorself and post the graph?

[KSSV]

Behaviour is the same but the time taken reduces that's it.

[Francesco Di Mauro]

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.

Answer 1

[Christine Tobler]

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.

[Christine Tobler]

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]

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!