How can I make this loop faster?

Why is this simple loop taking me so much time?

n=2^13;

idx=cell(2*n-1,1);

for i=1:2*n-1
    temp=zeros(i,2);
    for j=1:i
        if j>n
            idx1=0;
        else
            idx1=j;
        end
        if i-j+1>n
            idx2=0;
        else
            
            idx2=i-j+1;
        end
        temp(j,:)=[idx1,idx2];
    end
    idx{i}=temp;
end

Answer 1

[Ameer Hamza]

The matrices generated by your code just contain a linear array of integers. If you can tell, why do you want to create them in the first place, maybe I can suggest a better solution. Anyway, for the current code, try the following

n=2^13;
idxA=cell(2*n-1,1);
for i=1:2*n-1
    if i <= n
        temp = (1:i)';
    else
        temp = [(1:n)';zeros(i-n,1)];
    end
    idxA{i} = [temp flipud(temp)];
end

On my system, the execution time improved by about 8x.

tic
n=2^13;
idxA=cell(2*n-1,1);
for i=1:2*n-1
    if i <= n
        temp = (1:i)';
    else
        temp = [(1:n)';zeros(i-n,1)];
    end
    idxA{i} = [temp flipud(temp)];
end
toc

tic
n=2^13;
idxB=cell(2*n-1,1);
for i=1:2*n-1
    temp=zeros(i,2);
    for j=1:i
        if j>n
            idx1=0;
        else
            idx1=j;
        end
        if i-j+1>n
            idx2=0;
        else
            
            idx2=i-j+1;
        end
        temp(j,:)=[idx1,idx2];
    end
    idxB{i}=temp;
end
toc

isequal(idxA, idxB)

Result:

Elapsed time is 1.842785 seconds.
Elapsed time is 15.006841 seconds.

ans =

  logical

   1

[Mohamad Al Hassan]

I want to make a code that solve convolution equations, I want to solve for x such as:

G(f)*x(f)=F(f)

Where * is the convolution operator. So I need to set up the lhs of the equation based on the convolution formula (you can find it in the more about here: https://www.mathworks.com/help/matlab/ref/conv.html

[Ameer Hamza]

Does the code given in my answer work for your problem?

[Mohamad Al Hassan]

I have a second part that I want to make faster(it has a somewhat similar structure). After getting the indices from the first part I setup the equations as follows. It's also taking me so much time. G is a vector of complex numbers having a length n.

counter=0;

for i=n/2+1:n/2+n
    temp=idx{i};
    indices = find(temp(:,2)==0);
    temp(indices,:) = [];
    
    for j=1:length(temp)
        if temp(j,1)==0
            rhs=0;
        else
            rhs=G(temp(j,1));
        end
        mat(counter,temp(j,2))=rhs;
    end
    counter=counter+1;
end

[Ameer Hamza]

Are you trying to implement the convolution function?

[Mohamad Al Hassan]

Yes. I can't use the ifft(fft) trick since I need to obtain a system of equations to solve.

[Ameer Hamza]

Sorry, I don't understand this code, so it is difficult for me to suggest an optimization by vectorizing. This code runs quite slow, and maybe you need to rethink about your problem from basics. There might be some other efficient way to get the system of equations you want.