Avoiding nested loops

Hi everyone, I'm new to Matlab and trying to get rid of java/c programmer customs. I'm trying to do same thing without any loop.(To increase performance since I'm dealing with matrices of size O(50'000x50'000) ).

Basically I'm trying to find number of rows of the matrix A that have 1 at both column i and column j. I need these two for loop to have(/access to) all possible 2-column combinations of A.

Thanks in advance

PS: Matrix a is (binary) sparse vector.

MATLAB code
tic
%%step 1 create random matrix, t>10'000
A=logical(rand(t,n0)<p);
toc

%step 2 this step is really fast, nothing to change
tic
%finding weight of all columns, summing up 1's in each column
wi=sum(A);
%marking vectors that do not satisfy condition
marked=find(wi<=(1-delta)*u1);
toc

%step 3
tic
%finding number of rows of A that have 1 at both column i and column j
%by multiplying it with its transpose
B=sparse(A)'*sparse(A);
%getting numbers (i.e )
W=triu(B,1);
edges=(W>=meanvalue);
toc

I'm still trying to optimize step 1 and step 3.

[Paulo Silva]

Please format your code in a way that we can analyse properly and provide all variables we need to test the code.

[Walter Roberson]

Does the matrix have special properties, such as containing only the values 0 and 1 ?

[Mehmet Candemir]

Sorry I missed the formatting.

[Matt Fig]

And what is the variable mean? It would help if you would define all of the variables in your code so we know how to best help. Is n0==10,000? Are W and edges pre-allocated before the loops?

[Mehmet Candemir]

I updated the code, now it's more clear.

ps : 100'000>t >> n0>10'000

Answer 1

[Jan]

Some simple changes in your original implementation:

tic
W = zeros(n0, j - 1);  % Pre-allocate!
for j = 2:n0
  Aj = A(:, j);
  for i = 1:j-1
    W(i,j) = sum(and(A(:,i), Aj));
  end
end

edges = transpose(W >= meanValue);
toc

I do not use "mean", because it is a Matlab function. If A contains just zeros and ones, AND is faster than check if the sum equals 2. In addition you can save memory when using a LOGICALs as values of your sparse array. This is a better start point to create a more vectorized version:

tic
W = zeros(n0, j - 1);  % Pre-allocate!
for j = 2:n0
  W(1:j-1, j) = sum(bsxfun(@and, A(:, 1:j-1), A(:, j)));
end

edges = transpose(W >= meanValue);
toc

Answer 2

[Walter Roberson]

If the matrix contains only 0's and 1's, then the shortest code to do the counting is:

A.' * A

This will produce a symmetric square matrix whose dimensions are the number of columns of A.

Of course, it may be a problem to store a result matrix that large considering how large A is already. You can loop producing the results as

A.' * A(:,K)

[Walter Roberson]

Actually, if it contains only 0's and 1's, you can shorten to A'*A as there would be no difference between the complex conjugate transpose and a non-conjugate transpose.

[Mehmet Candemir]

Yes A is a binary matrix. (sparse matrix). And I updated the original question to make it easier to understand

[Walter Roberson]

Ah, different techniques are used for efficiency with sparse matrices. I'll have to think about this more. I do not have much experience with sparse matrices.