Vectorize loop to increase efficiency

Question

I have a 3 for loops and I would like if possible to vectorize the two inner loops.

for t=1:size(datesdaily1)
for i=1:size(secids,1)
    sum=0;
    if inc(t,i)==1 
    for j=1:size(secids,1)
        if inc(t,j)==1 
            sum=sum+weig1(t,j)*sqrt(Rates(t,j))*rhoneutral(i,j);         
        end
    end
    b(t,i)=sqrt(Rates(t,i))*sum/MRates(t,1);
    end
end    
end

Any idea on how to accomplish that? Here 'weig', 'inc' and 'Rates' are (size(datesdaily1) by size(secids,1)) matrixes and 'rhoneutral' is a (size(secids,1) by size(secids,1)) matrix.

I tried but I was not able to figure out how to do it ...

Actual full code:

for t=1:size(datesdaily1)

rho=NaN(size(secids,1),size(secids,1));
aux=datesdaily1(t,1);
windowlenght=252;
index=find(datesdaily==aux);
auxret=dailyret(index-windowlenght+1:index,:);

numerator=0;
denominator=0;

auxret(:,any(isnan(auxret))) = NaN;
rho = corr(auxret, 'rows','pairwise');
rho1 = 1 - rho;

w = weig1(t,:) .* sqrt(Rates(t,:));
x = w.' * w;
y = x .* rho;
z = x .* rho1;
numerator   = numerator   + nansum(nansum(y));
denominator = denominator + nansum(nansum(z));;

if not(denominator==0) 

alpha(t,1)=-(MRates(t,1)-numerator)/denominator;

%Stocks included
inc(t,:)=not(isnan(weig1(t,:).*diag(rho)'.*Rates(t,:)));

rhoneutral=rho-alpha(t,1).*(1-rho);


for i=1:size(secids,1)
    sum=0;
    if inc(t,i)==1 
    for j=1:size(secids,1)
        if inc(t,j)==1 
            sum=sum+weig1(t,j)*sqrt(Rates(t,j))*rhoneutral(i,j);         
        end
    end
    bet(t,i)=sqrt(Rates(t,i))*sum/MRates(t,1);
    end
end    
check(t,1)=nansum(weig1(t,:).*bet(t,:));



end
end

score 3 · Accepted Answer · edited May 23 '17 at 10:30

3

One vectorized approach using fast matrix multiplication in MATLAB -

%// Mask of valid calculations
mask = inc==1

%// Store square root of Rates which seem to be used rather than Rates itself
sqRates = sqrt(Rates)

%// Use mask to set invalid positions in weig1 and sqRates to zeros
weig1masked = weig1.*mask
sqRates = sqRates.*mask

%// Perform the sum calculations using matrix multiplication. 
%// This is where the magic happens!!
sum_vals = (weig1masked.*sqRates)*rhoneutral'  %//'

%// Perform the outermost loop calculations for the final output
b_vect = bsxfun(@rdivide,sum_vals.*sqRates,MRates)

Benchmarking

Here's a benchmark test specially dedicated to @Dmitry Grigoryev for the doubts put on vectorization for performance -

M = 200;
N = 200;

weig1 = rand(M,N);
inc = rand(M,N)>0.5;
Rates = rand(M,N);
rhoneutral = rand(N,N);
MRates = rand(M,1);

disp('--------------------------- With Original Approach')
tic
%// Code from the original approach
toc

disp('--------------------------- With DmitryGrigoryev Approach')
tic
%// Code from the DmitryGrigoryev's solution
toc

disp('--------------------------- With Much-Hated Vectorized Approach')
tic
%// Proposed matrix-multiplication approach in this solution
toc

Runtimes -

--------------------------- With Original Approach
Elapsed time is 0.104084 seconds.
--------------------------- With DmitryGrigoryev Approach
Elapsed time is 3.562170 seconds.
--------------------------- With Much-Hated Vectorized Approach
Elapsed time is 0.002058 seconds.

Posting runtimes for bigger datasizes might just be too embarrasing for loopy approches, way to go vectorization!!

edited May 23 '17 at 10:30

Community

1
1

answered Apr 30 '15 at 18:37

Divakar

218,885
19
262
358

Nice! Can't wait to see if this actually improves performance. – Dmitry Grigoryev Apr 30 '15 at 18:49
1

@DmitryGrigoryev Adding runtime test results for all the approaches soon! – Divakar Apr 30 '15 at 18:49
@DmitryGrigoryev Check out the test results. – Divakar Apr 30 '15 at 19:02
Well, I guess that overhead in Matlab code can explain why your approach is actually faster. What I fail to understand is why my approach is more than 10 times slower than the original. All I did is repeating the same loops twice, so I could imagine it would be twice as slow, but your results are unbelievable! – Dmitry Grigoryev Apr 30 '15 at 19:12
2

@DmitryGrigoryev First rule of vectorization: Never question a solution's performance that uses matrix multiplication in MATLAB :) Rest are of course taken on a case by case basis. – Divakar Apr 30 '15 at 19:14
I'm not questioning your solution, I compare mine with the original, and I can't see how it could be more than 10 times slower. – Dmitry Grigoryev Apr 30 '15 at 19:16
@Divakar, that worked perfectly. Actually I was only giving you a subset of my code. I have edited the original post with the full code. Can you help me on how should I implement your technique? – phdstudent Apr 30 '15 at 19:16
@DmitryGrigoryev Well that pre-computation part might have sucked in much of the performance. In a general case anway, looking to avoid loops in MATLAB is the preferred way and if matrix-multiplication could be used, it's like heaven! That's how high level languages like MATLAB, or even something like numpy works you know. – Divakar Apr 30 '15 at 19:18
@volcompt Try plugging in the suggested approach and see how it works? Did you do that? – Divakar Apr 30 '15 at 19:22
@Divakar, the issue is I don't think that plugging in would work give that I have some code before. I will try to do it, but I am a totally newbie in vectorization (any help is welcome)! Thanks for all your help! edit: I think I figured it out. Though the full code is still quite slow (though faster than before!) :) – phdstudent Apr 30 '15 at 19:26
I can't figure out how to vectorize the remaining of the code. Plugging in simply does not work given that the outer loop was vectorized as well. Still thanks. – phdstudent Apr 30 '15 at 19:34
@volcompt Remove the innermost two nested loops that calculate `bet` and put in the proposed approach until `sum_vals`. These `sum_vals` values should be the same as `bet`. Thus, you would end up with just one loop which would be the outermost loop of the exisiting code. Hope that helps. – Divakar Apr 30 '15 at 19:43
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/76669/discussion-between-volcompt-and-divakar). – phdstudent Apr 30 '15 at 19:54
Hi @Divakar, just wanted to thank you again for your help on this topic and on the chat. I know it has been more than a year. But I had to revisit this issue on a similar code, and your solution is flawless. I realized that I never answered you fully in the chat at the time. Here, again, my huge thank you. :) – phdstudent Nov 21 '16 at 18:57
1

@volcompt Ah that is sweet nevertheless! Good to see codes being re-used at other places, shows that the effort was worth it :) – Divakar Nov 21 '16 at 19:09

Vectorize loop to increase efficiency

1 Answers1

Benchmarking