Оптимизация взвешенной суммы разреженных матриц - PullRequest
1 голос
/ 01 марта 2011

Я приветствую любую помощь по следующей проблеме оптимизации кода:

У меня есть коллекция из N разреженных матриц одинаковых размеров ([s1 s2]), хранящихся в массиве ячеек A, и соответствующее количество скалярных весов, хранящихся в векторе w. Я хочу вычислить сумму всех матриц в A, взвешенную по значениям, хранящимся в w. Через итерации моей программы меняются только значения в w. Поэтому я могу априори вычислить количество ненулевых элементов в моем результате и предварительно выделить для него некоторую память, используя spalloc.
На данный момент у меня есть что-то вроде:

result = spalloc(s1,s1,number_of_non_zero);
for i=1:N
    result = result + w(i)*A{i};
end

Мне действительно нужно оптимизировать эту часть, которая на данный момент занимает большую часть вычислительного времени в моей программе (проверено с помощью инструментов профилирования).
Некоторая дополнительная информация:
Вышеприведенный код запускается миллионы раз, поэтому приветствуются даже незначительные улучшения.
Матрицы в A взяты из кода конечного элемента (1D или 2D)
- У меня нет проблем с удалением от структуры ячеек, если я могу сэкономить время (например, используя cell2mat(A))

Спасибо за любую подсказку о том, как ускорить эту часть кода.

A.

Ответы [ 2 ]

1 голос
/ 01 марта 2011

Не могу с уверенностью сказать, будет ли это решение более вычислительно эффективным, но стоит попробовать еще что-то ...

Если вам действительно нужно представлять свои матрицы как разреженные (т.е.слишком много памяти) и встроенное разреженное представление в MATLAB не дает желаемой производительности, тогда вы можете попытаться представить разреженные матрицы другим способом.В частности, вы можете представить их в виде матриц N-3, где первые два столбца содержат индексы строк и столбцов в матрице для всех ненулевых значений, а третий столбец содержит ненулевые значения.Вы можете преобразовать ваши данные в эту форму, используя функцию FIND примерно так:

for iMatrix = 1:numel(A)
  [r,c,v] = find(A{iMatrix});
  A{iMatrix} = [r c v];
end

Каждый раз, когда вам нужно вычислить взвешенную сумму этих матриц, вам сначала нужно умножить значенияпо весам:

B = A;  %# Store a temporary copy of A
for iMatrix = 1:numel(B)
  B{iMatrix}(:,3) = w(iMatrix).*B{iMatrix}(:,3);
end

Затем вы можете вычислить итоговую сумму, используя функцию ACCUMARRAY :

B = vertcat(B{:});  %# Convert B from a cell array to an N-by-3 matrix
result = accumarray(B(:,1:2),B(:,3));

Переменная result в этом случае будетбыть полной матрицей.Если вам нужно, чтобы result была разреженной матрицей, вы можете добавить дополнительные аргументы в вызове к ACCUMARRAY примерно так:

result = accumarray(B(:,1:2),B(:,3),[],[],[],true);
0 голосов
/ 01 марта 2011

Если вы преобразуете A в матрицу вместо массива ячеек, вы можете векторизовать цикл, используя некоторые RESHAPE и REPMAT акробатики. Представим, что у нас есть следующие данные:

>> A(:,:,1) = [1 0 0; 0 0 2; 0 0 0];
>> A(:,:,2) = [3 0 1; 0 3 0; 0 1 0]

A(:,:,1) =

     1     0     0
     0     0     2
     0     0     0


A(:,:,2) =

     3     0     1
     0     3     0
     0     1     0

>> w = [2; 3]

w =

     2
     3

Измените w, чтобы вы могли выполнить поэлементное умножение и затем сложить:

>> w = reshape(w, [1 1 length(w)])

w(:,:,1) =

     2


w(:,:,2) =

     3

>> w = repmat(w, [size(A,1) size(A,2) 1])

w(:,:,1) =

     2     2     2
     2     2     2
     2     2     2


w(:,:,2) =

     3     3     3
     3     3     3
     3     3     3

>> w .* A

ans(:,:,1) =

     2     0     0
     0     0     4
     0     0     0


ans(:,:,2) =

     9     0     3
     0     9     0
     0     3     0

>> sum(w .* A, 3)

ans =

    11     0     3
     0     9     4
     0     3     0
...