Как я могу векторизовать этот цикл в MATLAB

Question

У меня есть цикл, который выполняет итерацию по матрице и устанавливает все строки и столбцы только с одним ненулевым элементом ко всем нулям.

так, например, она будет преобразовать эту матрицу:

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

к матрице:

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

строк/столбцов 2 A имеет только 1 ненулевой элемент в ней, так что каждый элемент в строке/столбце 2 установлено значение 0 в A'

(предполагается, что матрицы всегда будут диагонально симметричными)

вот мой не-vectorised код:

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

Есть более эффективный способ написания этого кода в MATLAB?

EDIT:

меня попросили в комментариях для некоторых разъяснений, так что я буду принуждать.

Цель этого кода, чтобы удалить ребра из графа, которые ведут к вершине степени 1.

, если A матрица смежности, представляющая неориентированный граф G, затем строку или столбец этой матрицы, только один ненулевой элемент указывает, что строка/столбец представляет собой вершину первой степени, так как она имеет только один ребро, инцидентное ей.

Моя цель - удалить такие графы из графика, так как эти вершины никогда не будут посещены в решении проблемы, которую я пытаюсь решить, а уменьшение графика также уменьшит размер ввода для моего алгоритма поиска ,

@TimeString, я понимаю, что в примере, который вы дали, рекурсивное применение алгоритма к вашей матрице приведет к нулевой матрице, однако матрицы, которые я применяю для представления больших связанных графиков, так что никогда не будет такой случай. В ответ на ваш вопрос о том, почему я проверяю только количество элементов в строке, но очищает как столбцы, так и строки; это потому, что матрица всегда по диагонали симметрична, поэтому я знаю, что если что-то верно для строки, значит, это будет для соответствующего столбца ..

так, просто чтобы уточнить, используя другой пример:

Я хочу, чтобы превратить этот график G:

, представленный матрицей:

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

этому графу G':

представляемого этой матрица:

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

(я понимаю, что эта матрица должна быть на самом деле матрицей 3х3, потому что точка D была удалена, но я уже знаю, как сжать матрицу, в данном случае, мой вопрос о эффективно настройке столбцов/строк только с 1 ненулевого элемента все на 0)

я надеюсь, что это достаточно хорошее осветление ..

Answer 1

Не уверен, что если это действительно быстрее (зависит от Matlab-х JIT), но вы можете попробовать следующее:

Чтобы выяснить, какие столбцы (что эквивалентно, строки, так как матрица симметрична) имеет более чем один неприменение нулевого элемента:

sum(A ~= 0) > 1 

~= 0, вероятно, не необходимо в вашем случае, поскольку матрица состоит только из 1/0 элементов (графы, если я правильно понимаю).

Transform выше в диагональную матрицу для того, чтобы устранить нежелательные колонки:

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

И умножьте с А слева нулевых строк и справа нулевых столбцов:

res = D * A * D 

Answer 2

Благодаря предложение nimrodm использовать sum (A ~ = 0) вместо nnz, мне удалось найти лучшее решение, чем мое исходное

, чтобы очистить строки одним элементом, который я использую :

A(sum(A ~= 0) == 1,:) = 0; 

, а затем очистить столбцы с одним элементом:

A(:,sum(A ~= 0) == 1) = 0; 

для тех из вас, кто заинтересован, я сделал «крестики-TOC» сравнение на матрицу 1000 х 1000:

% establish matrix 
A = magic(1000); 
rem_rows = [200,555,950]; 
A(rem_rows,:) = 0; 
A(:,rem_rows) = 0; 

% insert single element into empty rows/columns 
A(rem_rows,500) = 5; 
A(500,rem_rows) = 5; 

% testing original version 
A_temp = A; 
for test = 1 
    tic 
    for ii = 1:length(A_temp) 
     if nnz(A_temp(ii,:)) == 1 
      A_temp(ii,:) = 0; 
      A_temp(:,ii) = 0; 
     end 
    end 
    toc 
end 

Elapsed time is 0.041104 seconds. 

% testing new version 
A_temp = A; 
for test = 1 
    tic 
    A_temp(sum(A_temp ~= 0) == 1,:) = 0; 
    A_temp(:,sum(A_temp ~= 0) == 1) = 0; 
    toc 
end 

Elapsed time is 0.010378 seconds 

% testing matrix operations based solution suggested by nimrodm 
A_temp = A; 
for test = 1 
tic 
B = diag(sum(A_temp ~= 0) > 1); 
res = B * A_temp * B; 
toc 
end 

Elapsed time is 0.258799 seconds 

так кажется, что одна строка версия, которую я придумал, вдохновленный предложением nimrodm, является самым быстрым

благодарим за вашу помощь!

Answer 3

Bsxfuning это -

A(bsxfun(@or,(sum(A~=0,2)==1),(sum(A~=0,1)==1))) = 0 

Пример запуска -

>> A 
A = 
    1  0  1  1 
    0  0  1  0 
    1  1  1  1 
    1  0  1  1 
>> A(bsxfun(@or,(sum(A~=0,2)==1),(sum(A~=0,1)==1))) = 0 
A = 
    1  0  1  1 
    0  0  0  0 
    1  0  1  1 
    1  0  1  1