스파 스 FFT 계산 속도 향상

Question

누군가 내 코드를 검토하고 tic와 toc 사이의 섹션 속도를 높이는 방법을 알 수 있기를 바랍니다. 아래 함수는 (1) 거의 모든 fft 계수 빈이 0 인 경우 (즉, 에서 10에서 1000까지의 bin이 300M bin이 0이 아니기 때문에) Matlab의 내장 함수보다 IFFT를 더 빨리 수행하려고 시도합니다. IFFT 결과의 중앙 1/3 만 유지됩니다 (첫 번째 및 마지막 세 번째는 삭제되므로 첫 번째 위치에서 계산할 필요가 없습니다).

입력 변수는 다음과 같습니다

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 어레이 (대역 당 즉 만 9 복소 FFT 계수; 18 PTS 측 파대를 고려) 인 경우 예를 들어, 및 DATAn=32781534, FFTn=33554432 (즉 2^25)를 후 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

당신은 매트랩 매트랩 스크립트 후 훨씬 빠르게 동작 외에, 그것은 또한 많은 사용 사례에 최적화 된 자사의 FFT 기능에 대한 컴파일 된 FFT 라이브러리 (http://www.fftw.org/)를 사용 명심해야한다. 첫 번째 단계는 c/C++로 코드를 작성하고 Matlab에서 사용할 수있는 mex 파일로 컴파일하는 것입니다. 그러면 코드의 속도가 적어도 엄청나게 빨라질 것입니다 (아마 더 많을 것입니다).

1. 당신은 당신이 FFT의 COEFFS의 대칭을 사용할 수 있도록 시간 시리즈는 실제 가치가 가정 게다가

   , 당신이 할 수있는 하나의 간단한 최적화는 두 가지를 고려하는 것입니다.

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 -files를 악용하여이 솔루션을 사용할 수 있습니다.