MATLAB: How to speed up this code consisting of 6 nested FOR loops

Question

Hi All,

I am trying to speed up the code below which consists of 6 nested FOR loops.

The purpose of this code is to fill a large, sparse matrix A with ones, and a large vector b with elements from a matrix dd of size TxTxN.

I have access to the Parallel Computing Toolbox, and ultimately this code will run on a cluster.

Any comments/suggestions would be greatly appreciated.

N= big number (e.g. 10000)
T=24;  
A=sparse(N*T*(T+1)/2,(N-1)*T+T); %matrix to be filled
b=sparse(N*T*(T+1)/2,1); %vector to be filled
tempT = (T+1)*T/2; % constant used in the loop
for j=1:N
for t1=1:T
   for t2=t1:T
       for t3=1:t2-t1+1
           rw = (j-1)*tempT + (t1-1)*(T-t1/2)+t2;
           cl = (j-1)*T+t1-1+t3;
           A(rw,cl) = 1;
             for t4=t1:t2
                 for t5=t4:t2
                 b(rw) = b(rw) + dd(t4,t5,j); % dd is given, size(dd)=TxTxN
                 end
             end
           end
       end
    end
    end

An earlier discussion on a simplified version of this with only 3 nested loops can be found here: http://www.mathworks.com/matlabcentral/answers/52005-how-to-transform-these-three-nested-for-loops-into-a-parfor-loop

Answer 1

Here's one proposal,

    N=1e4;
    T=24; 
    %dd=rand(T,T,N); %fake
    tempT = (T+1)*T/2;
    [T1,T2,T3]=ndgrid(1:T,1:T,1:T);
    idx = (T2>=T1) & (T3<=T2-T1+1);
    T1=T1(idx);
    T2=T2(idx);
    T3=T3(idx);
    nt=numel(T1);
    %Make row/col data
    RW=(T1-1).*(T-T1/2)+T2;
    CL=T1-1+T3;
    RW=bsxfun(@plus,RW,(0:N-1)*tempT);
    CL=bsxfun(@plus,CL,(0:N-1)*T);
    %For building b
    Z=zeros(nt,T^2);
    for ii=1:nt % A very small loop, no need to optimize
           [T4,T5]=ndgrid(T1(ii):T2(ii),T1(ii):T2(ii));
           idx=T5>=T4;
           T4=T4(idx);
           T5=T5(idx);
           ind=sub2ind([T,T],T4,T5);
           Z(ii,ind)=1;
    end
    ddd=Z*reshape(dd,[],N);
    A=sparse(RW,CL,1, N*T*(T+1)/2,N*T);
    b=sparse(RW(:),1,ddd(:),N*T*(T+1)/2,1);