Nested Loops issue

Hi, Please bear with me, as I am still learning with Matlab. I have a problem with efficiency of a nested loop in my Matlab code (I have copied and pasted this below).

 for ii=1:nn
        for jr1=1:length(PP.AII)
            sr1=(d(PP.AII{jr1})'*AA{ii}(PP.AII{jr1},PP.AII{jr1})*d(PP.AII{jr1}));
            dr1=dr1+sr1;
        end
end

When the number of elements of PP.AII increases, this loop becomes extremely slow. Ideally, I would like to write something like:

 for ii=1:nn
sr1=(d(PP.AII)'.*AA{ii}(PP.AII,PP.AII).*d(PP.AII));
sr1=sum(sr1);
end

However, Matlab will not allow this due to the fact that PP.AII consists of cell elements (for example, [90x1 double] [100x1 double] [90x1 double] [100x1 double]). I can find a way around this using the cell2mat and num2cell commands, however I feel that this is still inefficient due to introducing another nested loop, which seems to defeat the object.

Is there a way in which I can employ the dot command in order to speed up the above process? Failing this, does anyone have any other suggestions on how to speed up this area of code?

Any help is appreciated.

[Oleg Komarov]

How big is d (m by n size) and how big is PP (in terms of megabytes)? What system do you use (32/64 bit)?

Answer 1

[Jan]

At first I'd omit all repeated calculations output the loop(s) and use temporary variables:

PP_AII = PP.AII;
n = length(PP_AII);
for ii = 1:nn
  AAii = AA{ii};
  for jr1 = 1:n
    t1  = PP_AAI{jr1};
    t2  = d(t1);
    dr1 = dr1 + (t2' * AAii(t1, t1) * t2);
    % [EDITED] If t2 is a column vector, this is much faster:
    % dr1 = dr1 + (t2' * t2) * AAii(t1, t1);
  end
end

Please compare the speed with your original approach and the CELL2MAT method.

CELL2MAT is not efficient for larger cells (thousands of elements), because it seems to let the output grow dynamically instead of a clean pre-allocation. You can use FEX: Cell2Vec, but some reshaping / permutating might be necessary to create the wanted output.

[James]

Hi,

Thanks for the reply. I have tried this, however I do not really notice any increase in speed - maybe about 0.02 seconds on the overall runtime of the program.

[James]

Hi,

Thank you (again) for your reply. I find that the above does speed up the code. The standard runtime for nn equal to 200 was about 11.9 seconds, now it is 10.6 seconds. I will have a look at different elements of my code to see if I can implement the above throughout.

[Jan]

@James: I hoped that the speedup is higher than 10%. But 10 seconds seems to be surprisingly slow for this piece of code. What is "d()" and how large is n? Is it possible that the main time is spend in the function(?) d()? Please use the PROFILEr or TIC/TOC to find the real bottlenecks of the program.

If I assume that t2 is a [N x 1] vector, the processing is much faster if you reorder the elements:

dr1 = dr1 + (t2' * AAii(t1, t1) * t2);

==>

dr1 = dr1 + (t2' * t2) * AAii(t1, t1);

In the later case MATLAB uses an efficient BLAS method and the external multiplication is much cheaper.

[James]

Hi,

Apologies for the confusion. This was just a snippet of code that I have taken from a larger code - the reason that I only asked about this was because there are a few places where this type of computation appears. In general, this loop (in the profiler) seems to be taking about 1 seconds, whereas before it was taking about 2.4 seconds - therefore there is actually a fair bit of speedup.

In general, n would be about 4 or 8, whereas nn would be somewhere between 200 and 800. The above times were taken for n=4, nn=200.

[James]

Thanks for the extra reply. However, the 'improved' output does not correspond to the same dimensions as the original. (t2' * AAii(t1, t1) * t2) is just a scalar, however (t2' * t2) * AAii(t1, t1) will not be a scalar (in fact, the matrix dimensions do not actually agree).

[Jan]

This is the fact, if t1 is not a scalar, in opposite to my wrong assumptions.

Answer 2

[Andrei Bobrov]

variant 1

c = PP.AII;
sr1 = sum(cell2mat(cellfun(@(x)sum(cell2mat(arrayfun(@(i1)d(c{i1})'*x(c{i1},c{i1})*d(c{i1}),1:length(c),'un',0))),AA,'un',0)));

variant 2

nn = length(AA);
mm = length(PP.AII);
sr = zeros(nn,mm);
for ii=1:nn
   sr(ii,:) =arrayfun(@(i1)d(PP.AII{i1})'*AA{ii}(PP.AII{i1},PP.AII{i1})*d(PP.AII{i1}),1:mm);
end
sr1 = sum(sr(:));

[James]

Hi,

Thanks for the reply. However, if I try to include this in my matlab code, the runtime is actually increased (and pretty substantially as well). In general, nn is normall a value of between 200 and 800.

[James]

Update: Sorry, however I somehow managed to place the new line of code inside the 'nn' loop, which explains why it was taking so long. I have now got it out of this loop, however the code does not seem to work correctly with the above line?!?

[James]

Hi,

Thanks (again) for the reply. However, I am unsure that the above is equivalent to the original, as when I try to include the above in my code I find that it will not work?!?

[Jan]

@James: Please describe "it will not work" with any details. Solving problems is dramatically more efficient, if the problems are known already.

[James]

Hi,

When I stated that 'it will not work', what I meant was that when I tried to input the lines into my code, I found that when I tried to run the code I was obtaining an incorrect output. This is why I suggested that maybe the above lines are not quite equivalent to the original lines?

[Jan]

@Andrei: Your method evaluates "d(PP.AII{i1})" twice and "PP.AII{i1}" 4 times. Using a temp variable would be more efficient.

[Andrei Bobrov]

Dear Jan! I completely agree with your approach.