Can anyone help me optimize the if statements in For loops to make the code faster?

function [triu_adjacency,J_indices] = get_triu_adjacency(J_org, max_num_neighbors)


% J_org =[  0    -1    -1     1     2
%     -1     0    -1     1     2
%     -1    -1     0     1     2
%     1     1     1     0    -2
%     2     2     2    -2     0];

% 
% J_org =         [ 0, +2, +0, +1, +0, -1, -1
%        +2,  0, +0, -1, -1, +3, +0
%         +0, +0,  0, -2, +0, +1, +1
%         +1, -1, -2,  0, +2, +0, +0
%         +0, -1, +0, +2,  0, +0, +1
%         -1, +3, +1, +0, +0,  0, +0
%         -1, +0, +1, +0, +1, +0,  0];

J_org = full(J_org);
J = triu(J_org);
num_bits = length(J_org);
%max_neighbors = max(degree(graph(J_org)));
% max_neighbors =7

counter = 1;
zero_counter =[];

triu_adjacency = zeros(num_bits, max_num_neighbors);
J_indices = zeros(size(J));

for i= 1:num_bits
    n_neighbors = 1;

    col_list = J(1:i,i);
    for j = 1:length(col_list)
        if col_list(j)
            triu_adjacency(i,n_neighbors) = J_indices(j,i);
            n_neighbors = n_neighbors + 1;
        end
    end

    row_list = J(i,i+1:end);
    for j = 1:length(row_list)
        if row_list(j)
            triu_adjacency(i,n_neighbors) = counter;
            J_indices(i, j + i) = counter;
            counter = counter +1;
            n_neighbors = n_neighbors + 1;
        end
    end
    

     for k= n_neighbors:max_num_neighbors
            if isempty(zero_counter)
                triu_adjacency(i, k) = counter;
                zero_counter = counter;
                counter = counter +1;
            else
                triu_adjacency(i, k) = zero_counter;
                zero_counter = [];
            end
     end
end

end

[Walter Roberson]

It would help if the purpose of the code was documented.

[Nadatimuj]

Thank you! A little bit difficult to explain, but I will try.

I have a symmetric matrix (undirected graph). Let's say it's a 7x7 matrix. Let's say maximum degree of the graph is 4. I now want to generate a 7x4 matrix for hardware implementation.

The rules are:

1. Start from the J_org matrix.
2. Label the non-zero values one by one. For each row, do it upto max degree. If number of non-zero values in a row is less than max degrees, then spend a new label for that empty space.
3. Since it is originally a symmetric matrix, (i,j) value will be same as (j,i) values. So you will use the same label twice representaing the same value. This is true for the empty value label as well, use them twice.
4. J_indices report the unique labels on the upper triangle of J_org. Except empty labels.

Example Input:

J_org =

[0 2 0 1 0 -1 -1

2 0 0 -1 -1 3 0

0 0 0 -2 0 1 1

1 -1 -2 0 2 0 0

0 -1 0 2 0 0 1

-1 3 1 0 0 0 0

-1 0 1 0 1 0 0]

triu_adjacency =

[ 1 2 3 4

1 5 6 7

8 9 10 11

2 5 8 12

6 12 13 11

3 7 9 14

4 10 13 14]

J_indices =

[0 1 0 2 0 3 4

0 0 0 5 6 7 0

0 0 0 8 0 9 10

0 0 0 0 12 0 0

0 0 0 0 0 0 13

0 0 0 0 0 0 0

0 0 0 0 0 0 0]

Answer 1

[Jan]

The loops look fine. I'd omit the J=triu(J_org), because you use the upper triangle only inside the code

Vectorizing the inner loops increases the processing time by a factor of 2! See:

function [Adj,Index] = get_triu_adjacency(JS, nNeighbors)
% This is SLOWER then the original nested loops!!!
J     = full(JS) ~= 0;
nBits = length(J);
Adj   = zeros(nBits, nNeighbors);
Index = zeros(size(J));

c = 1;
z = nan;
for i = 1:nBits
   col = J(1:i, i);
   nc  = sum(col);
   Adj(i, 1:nc) = Index(col, i);
      
   row = J(i, i+1:nBits);
   nr  = sum(row);
   Adj(i,   nc+1:nc+nr)    = c:c+nr-1;
   Index(i, find(row) + i) = c:c+nr-1;
   
   c = c + nr - 1;
   n = nc + nr - 1;
   for k = n:nNeighbors
      if isnan(z)
         Adj(i, k) = c;
         z = c;
         c = c + 1;
      else
         Adj(i, k) = z;
         z         = nan;
      end
   end
end
end

I've simplified the names of the variables to reduce the clutter. Compare "n_neighbors" with a simple "n".

Setting z to NaN instead of the empty matrix might save some milliseconds. But the loop version seems to be efficient.

[Nadatimuj]

@Jan Thanks for the answer. Could you please explain why the following code runs faster using the "run" button but much slower using the "run and time" button?

clc
clearvars
close all


J_org = zeros(5000);
J = triu(J_org);

num_pbits = length(J);

 max_neighbors =6

counter = 1
zero_counter =[]

adjacency = zeros(num_pbits, max_neighbors);

J_indices = zeros(size(J));

for i= 1:num_pbits
    n_neighbors = 1;

    col_list = J(1:i,i);
    for j = 1:length(col_list)
        weight = col_list(j);
        if weight~=0
            adjacency(i,n_neighbors) = J_indices(j,i);
            n_neighbors = n_neighbors + 1;
        end
    end

    row_list = J(i,i+1:end);
    for j = 1:length(row_list)
        weight = row_list(j);
        if weight~=0
            adjacency(i,n_neighbors) = counter;
            J_indices(i, j + i) = counter;
            counter = counter +1;
            n_neighbors = n_neighbors + 1;
        end
    end
    

     for k= n_neighbors:max_neighbors
            if isempty(zero_counter)
                adjacency(i, k) = counter;
                zero_counter = counter;
                counter = counter +1;
            else
                adjacency(i, k) = zero_counter;
                zero_counter = [];
            end
     end
end

[Jan]

Measuring the timings reduces the pörocessing speed in general, not only for this code. To determine the need spent in each line, Matlab must record the timings after each command. Of course this is expensive.

In addition Matlab's profiler disables the JIT acceleration (at least partially): The JIT can reorder commands inside loops to improve the speed. But then Matlab cannot determine the time spent in a specific line anymore. This means, that the profiler has a strong influence on the processing speed - what a pity.

[Nadatimuj]

@Jan Got it, thanks for explaining.