How can I vectorize this function with nested FOR loop?

I have two for loops.L is one matrix of random numbers between 0,1 with dimension 24*100000.I want to vectorize it but i can't. because current code is very slow and take a long time.please help me.

K=zeros(100000,1);
T=zeros(100000,1);
for i=1:100000
    for j=1:100000
        K(j,1)=exp(-4*norm(L(:,i)-L(:,j))^2/norm(L(:,i))^2);
    end
    T(i,:)=sum(K)-1;
end

[Bob Thompson]

(L(:,i)-L(:,j))

This is what is going to make it difficult to vectorize. I believe there is a command to calculate this for you, but I'm not sure what exactly it is. It might be easier to do some research for this specifically, rather than the vectorization.

[Jan]

Why do you want to vectorize the code? There is no general benefit in doing this. Does the current code run too slow? Then an acceleration is the way to go. Vectorizing can improve the speed, but this is not in general.

To optimize the code, we need the chance to run it. Without meaningful input arguments, this is hard. So please provide L.

norm(x)^2 calculates an expensive square root only to square the result afterwards.

Do oyu have the parallel processing toolbox? A parfor might be very useful.

Answer 1

[Matt J]

Using mat2tiles

chunksize=10000;
Lc=mat2tiles(L.',[chunksize,24]); 
normL=mat2tiles(vecnorm(L,2,1),  [1, chunksize]);

N=numel(Lc);
Tc=cell(N);

for i=1:N
    for j=1:N
        E=pdist2(Lc{i},Lc{j})./normL{j};
        Tc{i,j}=sum( exp(-4*E.^2)  ,1);
    end
end


T=sum( cell2mat(Tc)  ,1).'-1;

[abtin irani]

At first thank you. at second i got this error ''Undefined function or variable 'vecnorm'.'' please help me. thanks a lot.

[Matt J]

What Matlab version are you using? In any case, try this revision:

chunksize=10000;
Lc=mat2tiles(L.',[chunksize,24]); 
normL=mat2tiles(sqrt(sum(L.^2,1)),  [1, chunksize]);

N=numel(Lc);
Tc=cell(N);
for i=1:N
    for j=1:N
        E=pdist2(Lc{i},Lc{j})./normL{j};
        Tc{i,j}=sum( exp(-4*E.^2)  ,1);
    end
end
T=sum( cell2mat(Tc)  ,1).'-1;

[abtin irani]

excuse me.I got this error ''Undefined function or variable 'mat2tiles' ''.matlab 2015a.

[Matt J]

You need to download it from the link I gave you.

[abtin irani]

excuse me where is your link?is there any other solution?

[Matt J]

Here it is: mat2tiles

[abtin irani]

excuse me . I got this error .Error using ./ Matrix dimensions must agree.Error in Untitled8 (line 37)

E=pdist2(Lc{i},Lc{j})./normL{j};

L is one matrix with dimension 24*10000

thank you.

[Matt J]

What Matlab version do you have?

[abtin irani]

2015a

[Matt J]

You should upgrade to R2016b or higher, if you can. Barring that, just modify this line

E=bsxfun(@rdivide, pdist2(Lc{i},Lc{j}) , normL{j} );

[abtin irani]

you helped me alot.thanks alot .it worked.in this line

E=bsxfun(@rdivide, pdist2(Lc{i},Lc{j}) , normL{j} );

it isn't normL{i}?can i ask you another thing.how can i vectorize this loop?

i=6
N=norm(L(:,i))/2;
P=zeros(10000,1);
for j=1:10000
    P(j,:)=norm(L(:,i)-L(:,j))/N;
    
end

thank you very much.

[Matt J]

you helped me alot.thanks alot .it worked.

You're welcome, but if so, please Accept-click the answer.

it isn't normL{i}?

I don't think so, but you can test both versions to be sure.

can i ask you another thing.how can i vectorize this loop?

That would just be,

P=pdist2(L(:,6).',L.').'/N

It may help you to read the pdist2 documentation to see how it works, and all its options.

[abtin irani]

excuse me.for chunksize=100000.I got this error:

Error using pdist2mex

Requested 100000x100000 (74.5GB) array exceeds maximum array size preference. Creation of arrays greater than this limit

may take a long time and cause MATLAB to become unresponsive. See array size limit or preference panel for more

information.

Error in pdist2 (line 343)

D = pdist2mex(X',Y',dist,additionalArg,smallestLargestFlag,radius);

Error in Untitled8 (line 37)

E=bsxfun(@rdivide, pdist2(Lc{i},Lc{j}) , normL{j} );

please help me.

[Matt J]

Yes, the error message makes sense. What question do you have about it?

[abtin irani]

how can i don't get this error?what is the solution for this error?thank you.

[Matt J]

Do not pass a matrix with 100000 rows to pdist2. This will attempt to create a 100000 x 100000 matrix, which the error message tells you is 75GB!!

[abtin irani]

so,what can i do if i don't use pdist2.is there any other solution instead of pdist2 that doesn't give this error? i want one solution for chunksize=1000000. thank you for your answers.

[Matt J]

Well, maybe the question to ask is, why are you making the chunksize larger, when you toldu us that the code already worked when the chunksize was just 10,000? Why change/fix something that is not broken?

Answer 2

[Jan]

n = 1000;
L = rand(24, n);
T = zeros(n, 1);
for i=1:n
    K     = exp(-4*sum((L(:,i) - L) .^ 2, 1) ./ sum(L(:,i).^2, 1));
    T2(i) = sum(K, 2) - 1;
end

This is 100 times faster than the original version for n=1000.

With parfor instead of for a further acceleration is possible.

To my surprise the above code is faster than this, which omits the repeated squaring:

T  = zeros(n,1);
L2 = L .^ 2;
for i=1:n
    K    = exp(-4*sum((L2(:,i) - 2*L(:,i).*L + L2), 1) ./ sum(L2(:,i), 1));
    T(i) = sum(K, 2)-1;
end

[abtin irani]

excuse me i got this error. Error using .*

Matrix dimensions must agree.

Error in Untitled8 (line 33)

K=exp(-4*sum((L2(:,i) - 2*L(:,i).*L + L2), 1) ./ sum(L2(:,i), 1));

[Jan]

You use Matlab < R2016b. Then:

 K = exp(-4*sum((L2(:,i) - bsxfun(@times, 2*L(:,i), L) + L2), 1) ...
     ./ sum(L2(:,i), 1));

But the first version seems to be faster.