help speeding up an incrementing loop

hi,

i'm trying to calculate some correlation factors using nested loop.

the equation im implementing is:

my parameters are:

H - 200*256 matrix

P - 200*370,000 matrix

AES_key_opt = 256

read_trc = 370,000

raw = 256*370,000 (calculated matrix)

now, i know i'm dealing with alot of data, but my question is if it possible to speed up somehow the relevant lines from the profiler?

relevant code part:

    % calculates the pearson correlation mat "raw" size "AES_key_opt","l_trc"
    for i = 1:AES_key_opt
        for j = 1:read_trc
            % claculate H' and P' for every "i" and "j"
            H_avg = H_C_sum(i)/n_trc;
            P_avg = P_C_sum(j)/n_trc;
            % numerator calculation
            numerator=0;
            for k = 1:n_trc
                numerator = numerator + (H(k,i) - H_avg)*(P(k,j) - P_avg);
            end
            % denumerator calculation
            denom_H = 0;
            denom_P = 0;
            for k = 1:n_trc
               denom_H = denom_H + (H(k,i) - H_avg)^2;
               denom_P = denom_P + (P(k,j) - P_avg)^2;
            end
            denominator = sqrt((denom_H*denom_P));
            % pearson correlation mat calculation
            raw(i,j) = numerator/denominator;
        end    
    end 

profiler:

I would be thankful for any help or tips

thanks

Answer 1

[Walter Roberson]

You have defined that you must use nested loops. That is what is loosing you most of your efficiency when you could be vectorizing.

You can make minor tweaks like extracting the (:,i) slice near the top of the for i loop and indexing that at k instead of indexing the array at (k,i) inside the triple loop, but I am not convinced that it would help in any meaningful way.

[Walter Roberson]

Though as Vladimir points out, pre-allocating raw() is recommended.

[Image Analyst]

Because he said "i'm trying to calculate some correlation factors using nested loop." I don't think that implied a definite requirement. It was just the way he first decided to tackle the problem. I think he's open to other, faster approaches.

[Walter Roberson]

The bar variables can be found by using mean()

Your denominators are closely related to the standard deviation. You do have sqrt() of the product of two terms, but because the terms are independent, you can separate the terms, sqrt(A) * sqrt(B), and the calculations being done individually then would be N * std(A,1) -- notice the second parameter of 1 to get the proper division (or you could use std() but change what you multiply by.)

Answer 2

[Vladimir Sovkov]

At the first glance, you can replace

             numerator=0;
             for k = 1:n_trc
                 numerator = numerator + (H(k,i) - H_avg)*(P(k,j) - P_avg);
             end

by

numerator = (H(1:n_trc,i) - H_avg)'*(P(1:n_trc,j) - P_avg);

as well as

             denom_H = 0;
             denom_P = 0;
             for k = 1:n_trc
                denom_H = denom_H + (H(k,i) - H_avg)^2;
                denom_P = denom_P + (P(k,j) - P_avg)^2;
             end

by

               denom_H = (H(1:n_trc,i) - H_avg)'*(H(1:n_trc,i) - H_avg);
               denom_P = (P(1:n_trc,j) - P_avg)'*(P(1:n_trc,j) - P_avg);

You can use ":" instead of "1:n_trc" if the corresponding array sizes exactly equal to n_trc.

You should also preallocate "raw" before the loop in order to avoid its sequential resizing: raw=zeros(...,...).

H_avg and P_avg are also recommended to compute before the loop as vectors, otherwise you compute the same values several times repeatedly.

Probably, fufther optimization is also possible.

Not all variables have clear sense (H_C_sum, P_C_sum, etc).

[tamir elazari]

i tried your change suggestions, but now it takes 4 times more time to complete.

[Walter Roberson]

These changes violate the stated constraint that nested loops must be used.

[tamir elazari]

hi Walter Roberson,

sorry if i wasnt clear, as english is not my native language.

by writing "nested loops" i just metioned the approach i took, i didnt mean it must be done with it.

[Vladimir Sovkov]

If no loops are necessary, I think that the matrix of Pearson statistics can be computed by a single line of code:

raw=normalize(H)'*normalize(P);

[Vladimir Sovkov]

raw=normalize(H)'*normalize(P)/size(H,1);