CODEWITHSUNDEEP
performancematlabmatrixvectorization
Itamar Katz
Itamar Katz

Reputation: 9655

Summation without a for loop - MATLAB

I have 2 matrices: V which is square MxM, and K which is MxN. Calling the dimension across rows x and the dimension across columns t, I need to evaluate the integral (i.e sum) over both dimensions of K times a t-shifted version of V, the answer being a function of the shift (almost like a convolution, see below). The sum is defined by the following expression, where _{} denotes the summation indices, and a zero-padding of out-of-limits elements is assumed:

S(t) = sum_{x,tau}[V(x,t+tau) * K(x,tau)]

I manage to do it with a single loop, over the t dimension (vectorizing the x dimension):

% some toy matrices
V = rand(50,50);
K = rand(50,10);
[M N] = size(K);

S = zeros(1, M);            
for t = 1 : N
  S(1,1:end-t+1) = S(1,1:end-t+1) + sum(bsxfun(@times, V(:,t:end),  K(:,t)),1);                
end

I have similar expressions which I managed to evaluate without a for loop, using a combination of conv2 and\or mirroring (flipping) of a single dimension. However I can't see how to avoid a for loop in this case (despite the appeared similarity to convolution).

Upvotes: 4

Views: 1827

Answers (2)

Divakar
Divakar

Reputation: 221764

Steps to vectorization

1] Perform sum(bsxfun(@times, V(:,t:end), K(:,t)),1) for all columns in V against all columns in K with matrix-multiplication -

sum_mults = V.'*K

This would give us a 2D array with each column representing sum(bsxfun(@times,.. operation at each iteration.

2] Step1 gave us all possible summations and also the values to be summed are not aligned in the same row across iterations, so we need to do a bit more work before summing along rows. The rest of the work is about getting a shifted up version. For the same, you can use boolean indexing with a upper and lower triangular boolean mask. Finally, we sum along each row for the final output. So, this part of the code would look like so -

valid_mask = tril(true(size(sum_mults)));
sum_mults_shifted = zeros(size(sum_mults));
sum_mults_shifted(flipud(valid_mask)) = sum_mults(valid_mask);
out = sum(sum_mults_shifted,2);

Runtime tests -

%// Inputs
V = rand(1000,1000);
K = rand(1000,200);

disp('--------------------- With original loopy approach')
tic
[M N] = size(K);
S = zeros(1, M);
for t = 1 : N
    S(1,1:end-t+1) = S(1,1:end-t+1) + sum(bsxfun(@times, V(:,t:end),  K(:,t)),1);
end
toc

disp('--------------------- With proposed vectorized approach')
tic
sum_mults = V.'*K; %//'
valid_mask = tril(true(size(sum_mults)));
sum_mults_shifted = zeros(size(sum_mults));
sum_mults_shifted(flipud(valid_mask)) = sum_mults(valid_mask);
out = sum(sum_mults_shifted,2);
toc

Output -

--------------------- With original loopy approach
Elapsed time is 2.696773 seconds.
--------------------- With proposed vectorized approach
Elapsed time is 0.044144 seconds.

Upvotes: 1

DGrady
DGrady

Reputation: 1105

This might be cheating (using arrayfun instead of a for loop) but I believe this expression gives you what you want:

S = arrayfun(@(t) sum(sum( V(:,(t+1):(t+N)) .* K )), 1:(M-N), 'UniformOutput', true)

Upvotes: 0

Related Questions