Ускорение разреженных БПФ вычислений - PullRequest
Новая
       6

Ускорение разреженных БПФ вычислений

2 голосов
/ 25 января 2011

Я надеюсь, что кто-то может просмотреть мой код ниже и предложить подсказки, как ускорить раздел между тик и ток. Приведенная ниже функция пытается выполнить IFFT быстрее, чем встроенная функция Matlab, поскольку (1) почти все ячейки с коэффициентом fft равны нулю (т. Е. Ячейки с 10 до 1000 из чисел 10M до 300M не ноль), и (2) сохраняется только центральная треть результатов IFFT (первая и последняя треть отбрасываются - поэтому нет необходимости вычислять их в первую очередь).

Входные переменные: 

fftcoef = complex fft-coef 1D array (10 to 1000 pts long)
bins = index of fft coefficients corresponding to fftcoef (10 to 1000 pts long)
DATAn = # of pts in data before zero padding and fft (in range of 10M to 260M)
FFTn = DATAn + # of pts used to zero pad before taking fft (in range of 16M to 268M) (e.g. FFTn = 2^nextpow2(DATAn))

В настоящее время этот код занимает на несколько порядков больше, чем функциональный подход Matlab ifft, который вычисляет весь спектр, а затем отбрасывает 2/3 из него. Например, если входными данными для fftcoef и bin являются 9x1 массивы (т.е. только 9 комплексные коэффициенты fft на боковую полосу; 18 pts при рассмотрении обеих боковых полос) и DATAn=32781534, FFTn=33554432 (то есть 2^25), тогда подход ifft занимает 1.6 секунд, тогда как цикл ниже занимает 700 секунд.

Я избегал использования матрицы для векторизации цикла nn, так как иногда размер массива для fftcoef и bin может быть до 1000 pts длиной, а матрица 260Mx1K будет слишком большой для памяти, если только она не будет как-то расстались.

Любой совет очень ценится! Заранее спасибо. 

function fn_fft_v1p0(fftcoef, bins, DATAn, FFTn)

fftcoef = [fftcoef; (conj(flipud(fftcoef)))];     % fft coefficients
bins = [bins; (FFTn - flipud(bins) +2)];          % corresponding fft indices for fftcoef array

ttrend = zeros( (round(2*DATAn/3) - round(DATAn/3) + 1), 1); % preallocate

start = round(DATAn/3)-1;

tic;
for nn = start+1 : round(2*DATAn/3)  % loop over desired time indices
  % sum over all fft indices having non-zero coefficients
  arg = 2*pi*(bins-1)*(nn-1)/FFTn;
  ttrend(nn-start) = sum( fftcoef.*( cos(arg) + 1j*sin(arg)); 
end
toc;

end

Ответы [ 2 ]

3 голосов
/ 25 января 2011

Вы должны иметь в виду, что Matlab использует скомпилированную библиотеку fft (http://www.fftw.org/) для своих функций fft, которая, помимо работы намного быстрее, чем скрипт Matlab, хорошо оптимизирована для многих случаев использования.Первым шагом может быть написание вашего кода на языке c / c ++ и его компиляция в виде mex-файла, который вы можете использовать в Matlab. Это, несомненно, ускорит ваш код как минимум на порядок (возможно, больше).

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

  1. Вы предполагаете, что ваш временной ряд является действительным значением, поэтому вы можете использовать симметрию коэффициентов БПФ.
  2. Ваше времясерия, как правило, намного длиннее, чем ваш вектор коэффициентов БПФ, поэтому лучше выполнять итерации по бинам, а не по временным точкам (таким образом, векторизовав более длинный вектор).

Эти две точки переводятся в следующий цикл:

nn=(start+1 : round(2*DATAn/3))';
ttrend2 = zeros( (round(2*DATAn/3) - round(DATAn/3) + 1), 1);
tic;
for bn = 1:length(bins)
     arg = 2*pi*(bins(bn)-1)*(nn-1)/FFTn; 
     ttrend2 = ttrend2 +  2*real(fftcoef(bn) * exp(i*arg)); 
end
toc;

Обратите внимание, что вы должны использовать этот цикл до того, как разверните bins и fftcoef, поскольку симметрия уже принята в соответствиент.Этот цикл занимает 8,3 секунды для запуска с параметрами из вашего вопроса, в то время как мой компьютер занимает 141,3 секунды для запуска с вашим кодом.

0 голосов
/ 21 ноября 2016

Я разместил вопрос / ответ на Ускорение сокращения FFTW, чтобы избежать массивного заполнения нулями , которое решает проблему для случая C ++ с использованием FFTW. Вы можете использовать это решение, используя mex -файлы.

...