Ускорение индекса в огромной разреженной матрице во время цикла в MATLAB - PullRequest
Новая
       72

Ускорение индекса в огромной разреженной матрице во время цикла в MATLAB

0 голосов
/ 03 ноября 2019

Мне нужно построить огромную разреженную матрицу в итерациях. Код выглядит следующим образом: 

function Huge_Matrix = Create_Huge_Matrix(len, Weight, Index)

    k = size(Weight,1);

    Huge_Matrix = spalloc(len, len,floor(len*k));


    parfor i = 1:len
        temp = sparse(1,len);
        ind = Index(:,i);
        temp(ind) = Weight(:,i);
        Huge_Matrix(i,:) = temp;
    end


    Huge_Matrix = Huge_Matrix + spdiags(-k*ones(len,1),0,len,len);


end

Как показано, len - это размер высоты * веса входного изображения, для изображения 200 * 200 len равно 40000! И я назначаю Weight в эту огромную матрицу в соответствии с положением, хранящимся в Index. Несмотря на то, что я использую parfor для ускорения цикла, скорость очень низкая.

Сначала я также пытаюсь создать полную матрицу, кажется, что код может стать быстрее, но память ограничена. Есть ли другой способ ускорить код? Заранее спасибо!

1 Ответ

4 голосов
/ 03 ноября 2019

Как говорит @ CrisLuengo в комментариях, вероятно, есть лучший способ сделать то, что вы пытаетесь сделать, чем создать матрицу 40kx40k, но если у вас есть длясоздайте большую разреженную матрицу, лучше позволить MATLAB сделать это за вас.

Функция sparse имеет сигнатуру, которая принимает списки строк, столбцов и соответствующие значения для ненулевых элементовматрица:

S = sparse(i,j,v) создает разреженную матрицу S из триплетов i, j и v, такую ​​что S(i(k),j(k)) = v(k). В выходной матрице max(i)-by-max(j) выделено место для ненулевых элементов length(v). sparse складывает вместе элементы в v, которые имеют повторяющиеся индексы в i и j.

Если входные данные i, j и v являются векторами или матрицами, онидолжно иметь одинаковое количество элементов. Альтернативно, аргумент v и / или один из аргументов i или j могут быть скалярами.

Таким образом, мы можем просто передать Index в качестве индексов строки и Weight как значения, так что все, что нам нужно, это массив индексов столбцов того же размера, что и Index: 

col_idx = repmat(1:len, k, 1);
Huge_Matrix = sparse(Index, col_idx, Weight, len, len);

(последние два параметра определяют размер разреженной матрицы.)

Следующий шаг - создать еще одну большую разреженную матрицу и добавить ее к первой. Это кажется расточительным, так почему бы просто не добавить эти записи в существующие массивы перед созданием матрицы?

Вот последняя функция: 

function Huge_Matrix = Create_Huge_Matrix(len, Weight, Index)

   k = size(Weight,1);

   % add diagonal indices/weights to arrays
   % this avoids creating second huge sparse array 
   Index(end+1, :) = [1:len];
   Weight(end+1, :) = -k*ones(1,len);

   % create array of column numbers corresponding to each Index
   % make k+1 rows because we've added the diagonal
   col_idx = repmat(1:len, k+1, 1);

   % let sparse do the work
   Huge_Matrix = sparse(Index, col_idx, Weight, len, len);

end
...