スパースFFT計算の高速化

Question

私は以下のコードを見直して、チックとトックの間のセクションをスピードアップするヒントを提供したいと考えています。以下の関数は、（1）fft係数ビンの殆どがゼロである（すなわち、,〜300M個のビンが0でない〜1000個のビン）、（2）ビンが0であるため、Matlabのビルトイン関数より高速にIFFTを実行しようとします。 IFFT結果の中央3分の1だけが保持されます（最初と最後の3分の1は破棄されるため、最初に計算する必要はありません）。

入力変数は以下のとおりです。

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)) 

現在、このコードが長く、スペクトル全体がそれの2/3年代を破棄計算のMatlabのifft関数アプローチよりも数桁をとります。例えば、fftcoefとビンのための入力データが9x1配列である場合、（すなわち2^25）（側波帯あたりすなわちのみ9複雑なFFT係数の両方の側波帯を考慮した場合18 PTS）、及びDATAn=32781534、FFTn=33554432、次にIFFTアプローチは、一方1.6秒かかり下のループは700秒を引き継ぎます。

fftcoefとbinsの配列サイズが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 

Answer 1

あなたは、MATLABがMATLABスクリプトその後、はるかに高速に動作させる以外にも、それは、多くのユースケース用に最適化され、そのFFT関数、用にコンパイルFFTライブラリ（http://www.fftw.org/）を使用して心に留めておく必要があります。だから最初のステップはあなたのコードをc/C++で書いて、それをMatlab内で使うことができるmexファイルとしてコンパイルすることです。それは確かに少なくともあなたのコードのスピードを上げるでしょう（もっと多分）。

1. あなたは、あなたは、FFT coeffsの対称性を利用することができますので、お時間のシリーズは、本物の、評価されていると仮定します。そのほかに

   は、あなたが行うことができます1つの単純な最適化は、2つのことを考慮しています。

2. あなたの時系列は通常、あなたのfft coeffsベクトルよりもはるかに長いので、時間点の代わりにビンを反復する方が良い（長いベクトルをベクトル化する方がよい）。

これら二点は、次のループに翻訳されています

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秒かかります。

Answer 2

Accelerating FFTW pruning to avoid massive zero paddingに質問/回答を投稿しました。この質問/回答は、FFTWを使用しているC++の問題を解決しています。 mexファイルを利用してこのソリューションを使用できます。