How can I vectorise this loop in MATLAB

Question

I have a loop that iterates over a matrix and sets all rows and columns with only one non-zero element to all zeroes.

so for example, it will transform this matrix:

A = [ 1 0 1 1
      0 0 1 0
      1 1 1 1
      1 0 1 1 ]

to the matrix:

A' = [ 1 0 1 1
       0 0 0 0
       1 0 1 1
       1 0 1 1 ]

row/column 2 of A only has 1 non zero element in it, so every element in row/column 2 is set to 0 in A'

(it is assumed that the matrices will always be diagonally symmetrical)

here is my non-vectorised code:

for ii = 1:length(A)
    if nnz(A(ii,:)) == 1
        A(ii,:) = 0;
        A(:,ii) = 0;
    end
end

Is there a more efficient way of writing this code in MATLAB?

EDIT:

I have been asked in the comments for some clarification, so I will oblige.

The purpose of this code is to remove edges from a graph that lead to a vertex of degree 1.

if A is the adjacency matrix representing a undirected graph G, then a row or column of that matrix which only has one non-zero element indicates that row/column represents a vertex of degree one, as it only has one edge incident to it.

My objective is to remove such edges from the graph, as these vertices will never be visited in a solution to the problem I am trying to solve, and reducing the graph will also reduce the size of the input to my search algorithm.

@TimeString, i understand that in the example you gave, recursively applying the algorithm to your matrix will result in a zero matrix, however the matrices that I am applying it to represent large, connected graphs, so there will never be a case like that. In response to your question as to why I only check for how many elements in a row, but the clear both columns and rows; this is because the matrix is always diagonally symmetrical, so i know that if something is true for a row, so it will be for the corresponding column..

so, just to clarify using another example:

I want to turn this graph G:

represented by matrix:

A = [ 0 1 1 0
      1 0 1 0
      1 1 0 1
      0 0 1 0 ]

to this graph G':

represented by this matrix:

A' = [ 0 1 1 0
       1 0 1 0
       1 1 0 0
       0 0 0 0 ]

(i realise that this matrix should actually be a 3x3 matrix because point D has been removed, but i already know how to shrink the matrix in this instance, my question is about efficiently setting columns/rows with only 1 non-zero element all to 0)

i hope that is a good enough clarification..

I feel your question can contradict to itself, plus your solution doesn't really solve the question you asked. 1) What is the expected answer of A = [1 1 0; 0 1 1; 0 0 1]? I think recursively I should get a zero matrix. 2) In your solution code, why do you just check how many 1s in a row, but also clear the entire column? Clarify it? — TimeString
Got it, that's why you said A is symmetric which I didn't capture earlier — TimeString

nimrodm nimrodm · Accepted Answer · 2015-11-10T04:26:11

Not sure if it's really faster (depends on Matlab's JIT) but you can try the following:

To find out which columns (equivalently, rows, since the matrix is symmetric) have more than one non zero element use:

sum(A ~= 0) > 1

The ~= 0 is probably not needed in your case since the matrix consists of 1/0 elements only (graph edges if I understand correctly).

Transform the above into a diagonal matrix in order to eliminate unwanted columns:

D = diag(sum(A~=0) > 1)

And multiply with A from left to zero rows and from right to zero columns:

res = D * A * D

How can I vectorise this loop in MATLAB

3 Answers