Мой код для алгоритма Штрассена в Matlab работает слишком медленно

это мой первый раз, когда задаю вопрос, поэтому, пожалуйста, простите меня, если я что-то не так.

Я пытаюсь закодировать алгоритм Штрассена в Matlab, и он вроде работает, но он очень медленный (в зависимости от отсечки он уже может занимать больше секунды для матриц 64x64).

Это медленнее, чем наивная реализация (с 3 циклами). Есть ли что-то, что я делаю ужасно неправильно? Ниже приведена функция, ввод уже имеет правильный размер (2 ^ n)

function [ D ] = ActualStrassen( PaddedA, PaddedB )

   [m n] = size(PaddedA);

   if n < 5
      D = PaddedA*PaddedB;

   else
      A11 = PaddedA( 1:n/2     , 1:n/2    );
      A12 = PaddedA( 1:n/2     , n/2+1:end);
      A21 = PaddedA( n/2+1:end , 1:n/2    );
      A22 = PaddedA( n/2+1:end , n/2+1:end);
      B11 = PaddedB( 1:n/2     , 1:n/2    );
      B12 = PaddedB( 1:n/2     , n/2+1:end);
      B21 = PaddedB( n/2+1:end , 1:n/2   );
      B22 = PaddedB( n/2+1:end , n/2+1:end);

      M1=ActualStrassen( A11 + A22 , B11 + B22);
      M2=ActualStrassen( A21 + A22 , B11      );
      M3=ActualStrassen( A11       , B12 - B22);
      M4=ActualStrassen( A22       , B21 - B11);
      M5=ActualStrassen( A11 + A12 , B22      );
      M6=ActualStrassen( A21 - A11 , B11 + B12);
      M7=ActualStrassen( A12 - A22 , B21 + B22);

      D11= M1 + M4 - M5 + M7;
      D12= M3 + M5;
      D21= M2 + M4;
      D22= M1 - M2 + M3 + M6;

      D = [D11, D12; D21, D22];

   end
end

matlab performance strassen
person salicum    schedule 04.10.2014    source источник
comment
Я предлагаю вам подсчитать количество (элементарных) сложений и умножений, которые ваш код фактически использует для вычисления произведения двух массивов 64 * 64, и сравнить с числом для «наивного» алгоритма O(n^3). Затем подумайте о затратах времени на все эти рекурсивные вызовы ActualStrassen и требуемое для них выделение памяти. Затем немного прочитайте SO и посмотрите ответы на похожие вопросы, например stackoverflow.com/questions/13559928/ Это относится к реализации C++, но большая часть принятого ответа актуальна для вас   -  person High Performance Mark    schedule 05.10.2014
comment
Итак, мой компьютер работает быстро, но tic; A = rand(64); B = rand(64); D = ActualStrassen(A,B); toc дает Elapsed time is 0.052790 seconds.. Нам очень далеко до секунды.   -  person Jonathan H    schedule 05.10.2014
comment
в Matlab внутренние подпрограммы сильно оптимизированы. Количество выполненных операторов, вероятно, будет иметь такой же эффект, как и то, что в них делается. С точки зрения скорости, встроенный матричный множитель почти наверняка будет самым крутым.   -  person camelccc    schedule 05.10.2014