Nested for loop performance speed up

Hi everybody,

I have this first version, working, of a analysis loop. This netsted for loop is simply analysing a geometric problem involving points.

The problem is, it is much too slow, as a big amount of points needs to be processed.

Previous calculation and assignment, causing the following vectors:

% Pre allocation/calculations
A = 3 x 8000 
B = 3 x 1e6

% ....
% ....
% ....
C = [0;0;0];
alpha = 0;
beta = 0;
vis = 50;
D = zeros(size(B,2),size(A,2));

for i=1:size(A,2)
    for k=1:size(B,2)
        C = A(:,i) - B(:,k);
        alpha = acos(dot(A(:,i),C)/norm(A(:,i))/norm(C));
        beta = pi-acos(dot(B(:,k),C)/norm(B(:,k))/norm(C));
        if((alpha <= (vis)) && beta >= pi/2)
            D(k,i) = 1;            
        else
            D(k,i) = 0;
        end
    end
end

Vectorizing this loop appears to be quite difficult, at least for me, e.g. because of the functions (dot product, norm etc,) beeing called within the loop. I got stuck here when trying to vectorize.

Are there any ideas or concrete approaches on your minds to inprove this loops' performance?

Thanks!

[Mario Malic]

Hi,

dot allows entry of matrices, which would probably simplify and speed up the code as well. See the documentation how to properly call it.

Answer 1

[Matt J]

With the data sizes you've shown, the final result D will be a 7GB logical matrix. That seems like a non-starter. If you can reduce size(A,2) and size(B,2) to more practical values, however, then the loops can be vectorized as follows:

A=reshape(A,3,1,[])

C= A-B;
C=C./vecnorm(C,2,1);

A=A./vecnorm(A,2,1);
B=B./vecnorm(B,2,1);

alpha=squeeze( acos( sum(A.*C,1) ) );
beta=pi-squeeze( acos( sum(B.*C,1) ) );

D=alpha<=vis & beta>=pi/2;

[Bruno Luong]

I would think (not carefully check)

D=alpha>=cos(vis) & beta>=0; % 0 is cos(pi/2);

[Matt J]

One way to manage the large memory would be to divide A into a relatively small number of pages, and loop over them:

Apages=reshape(A,3,100,[]); N=size(A,3);


B=B./vecnorm(B,2,1);
Bn=B./vecnorm(B,2,1);

D=cell(1,N);

for i=1:N

    a=reshape( Apages(:,i), 3,1,[]);
    an=a./vecnorm(a,2,1);
        
    C= a-B;
    C=C./vecnorm(C,2,1);
    
    alpha=squeeze( acos( sum(an.*C,1)) );
    beta=pi-squeeze( acos(sum(Bn.*C,1)) );
    
    D{i}=alpha<=vis & beta>=pi/2;

end

D=cell2mat(D);

[Matt J]

@Bruno Luong Yep. You're right. I think I fixed it.

[Bruno Luong]

Stil not right : in the test you compare the correlation (unitless) with the angle (radian).

[Matt J]

No, I nserted the acos() operators.

[Bruno Luong]

Ah I see. I would though for better speed, we do not need to call acos on huge array, but compare correlation instead.