MATLAB - Эффективные методы для заполнения матриц с использованием информации в других (разреженных) матриц?

Question

Извиняюсь за неудобное название, вот более конкретное описание проблемы. У меня есть большая (например, 10 ^ 6 x 10 ^ 6) разреженная симметричная матрица, которая определяет связи между узлами.

например. Матрица A = [0 1 0 0 0; 1 0 0 2 3; 0 0 0 4 0; 0 2 4 0 5; 0 3 0 5 0] будет описывать систему из 5 узлов, так что узлы 1 и 2 соединяются номером связи A(1,2) = 1, узлы 3 и 4 соединяются номером связи A(3,4) = 4 и т. Д.

Я хочу сформировать две новые матрицы. Первый, B, будет перечислять узлы, подключенные к каждому узлу (т. Е. Каждая строка i из B имеет элементы, заданные find(A(i,:)) и дополненные нулями в конце, если необходимо), а вторая, C, перечислит связи, связанные с этот узел (т. е. каждая строка i из C имеет элементы, заданные nonzeros(A(i,:)), при необходимости снова дополненные).

например. для вышеприведенной матрицы A я бы хотел сформировать B = [2 0 0; 1 4 5; 4 0 0; 2 3 5; 2 4 0] и C = [1 0 0; 1 2 3; 4 0 0; 2 4 5; 3 5 0]

Текущий код:

B=zeros(length(A), max(sum(spones(A))))
C=zeros(length(A), max(sum(spones(A))))
for i=1:length(A)
    B(i,1:length(find(A(i,:)))) = find(A(i,:));
    C(i,1:length(nonzeros(A(i,:)))) = nonzeros(A(i,:));
end

, который работает, но медленно для большой длины (A). Я пробовал другие формулировки, но все они включают циклы и не дают особых улучшений.

Как мне сделать это без циклического перебора строк?

Answer 1

Я знаю, что это трудно читать, но этот код является векторизованной версией вашего кода:

[ i j k ] = find(A);
A2=(A~=0);
j2=nonzeros(cumsum(A2,2).*A2);
C2=accumarray([i,j2],k)
k2=nonzeros(bsxfun(@times,1:size(A,2),A2));
B2=accumarray([i,j2],k2);

Попробуйте и скажите мне, работает ли он для вас.

Answer 2

Хм. Не уверен, как векторизовать (find возвращает линейные индексы при заданной матрице, а это не то, что вам нужно), но вы пробовали это:

B=zeros(length(A), 0);
C=zeros(length(A), 0);
for i=1:length(A)
    Bi = find(A(i,:));
    B(i,1:length(Bi)) = Bi;
    Ci = nonzeros(A(i,:));
    C(i,1:length(Ci)) = Ci;
end

Я сделал два изменения:

• удалено обращение к спонам (кажется ненужным; снижение производительности, необходимое для увеличения числа столбцов в B и C, вероятно, минимально)
• кэшированный результат поиска () и ненулевых значений (), поэтому они не вызываются дважды