FFTW

FFTW
FFTW
The FFTW logo
FFTW 로고
개발자마테오 프리고와 스티븐 G. 존슨
초기 릴리즈1997년 3월 24일(1997-03-24)
안정된 릴리스
3.3.10[1] / 2021년 9월 15일; 10개월 전 (2021년 9월 15일)
저장소
기입처C, OCaml
유형수치 소프트웨어
면허증.GPL, 상용
웹 사이트www.fftw.org Edit this on Wikidata

서부에서의 가장 빠른 푸리에 변환(FFTW)은 매사추세츠 [2][3][4]공과대학의 마테오 프리고와 스티븐 G. 존슨이 개발한 이산 푸리에 변환(DFT)을 계산하는 소프트웨어 라이브러리입니다.

FFTW는 FFT(Fast Fourier Transform)의 가장 빠른 자유 소프트웨어 구현 중 하나입니다.임의의 크기와 치수의 실제 및 복소수 배열에 FFT 알고리즘을 구현합니다.

도서관

FFTW는 다양한 알고리즘을 지원하고 특정 상황에서 선호될 것으로 추정하거나 측정하는 알고리즘(변환의 특정 분해)을 선택하여 데이터를 신속하게 변환합니다.소수 계수가 작은 크기의 배열에서 가장 잘 작동하며, 2의 거듭제곱이 최적이고 큰 소수가 최악의 경우입니다(단, O(n log n)).복합 크기의 변환을 더 작은 변환으로 분해하기 위해 Cooly의 여러 변형 중 하나를 선택합니다.Tukey FFT 알고리즘(다른 인수 분해 및/또는 다른 메모리 액세스 패턴에 해당)은 프라임 크기의 경우 Rader [2]또는 Bluestein의 FFT 알고리즘을 사용합니다.변환이 충분히 작은 크기의 하위 변환으로 분할되면 FFTW는 코드 생성에 의해 생성된 작은 크기(런타임이 아닌 컴파일 시)에 대해 하드 코딩된 미연 FFT를 사용합니다. 이러한 루틴은 Cooly를 포함한 다양한 알고리즘을 사용합니다.Tukey variants, Rader's algorithm 및 프라임 팩터 FFT 알고리즘.[2]

충분히 많은 수의 반복 변환에서는 특정 어레이 크기 및 플랫폼에서 지원되는 알고리즘의 일부 또는 전부를 측정하는 것이 좋습니다.저자들이 "지혜"라고 부르는 이러한 측정은 나중에 사용하기 위해 파일이나 문자열에 저장할 수 있습니다.

FFTW에는 "기본 FFTW 아키텍처의 유연성을 최대한 드러내는" "구루 인터페이스"가 있습니다.이를 통해 특히 단일 호출(예: 데이터가 메모리에 인터리빙되는 곳)에서 다차원 변환과 다중 변환을 수행할 수 있습니다.

FFTW는 순서가 다른 변환(MPI(Message Passing Interface) 버전 사용)을 제한적으로 지원합니다.데이터 순서 변경으로 인해 오버헤드가 발생하며, 임의 크기 및 치수의 인플레이스 변환의 경우 이러한 오버헤드를 피할 수 없습니다.이 오버헤드는 어떤 변환이 중요한지는 문서화되지 않았습니다.

FFTW는 GNU General Public License에 따라 라이선스가 부여됩니다.또한 MIT에 의해[5] 상용 라이선스(최대 $12,500의 비용으로)되어 있으며, FFT를 계산하기 위한 상용[6] MATLAB 매트릭스 패키지에 사용됩니다. FFTW는 C 언어로 작성되지만 Fortran 및 Ada 인터페이스와 함께 몇 가지 다른 언어용 인터페이스가 있습니다.라이브러리 자체는 C이지만 코드는 실제로는 '라는 프로그램에서 생성됩니다.genfft'는 [7]OCaml로 표기되어 있습니다.

1999년 FFTW는 수치 소프트웨어 부문 J. H. 윌킨슨 상을 수상했습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "The FFTW Release Notes". Retrieved 16 September 2021.
  2. ^ a b c Frigo M, Johnson SG (February 2005). "The design and implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301.
  3. ^ Frigo M, Johnson SG (1998). FFTW: an adaptive software architecture for the FFT. Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing. Vol. 3. pp. 1381–1384. CiteSeerX 10.1.1.47.8661. doi:10.1109/ICASSP.1998.681704. ISBN 978-0-7803-4428-0.
  4. ^ Johnson SG, Frigo M (September 2008). "ch.11: Implementing FFTs in practice". In C. S. Burrus (ed.). Fast Fourier Transforms. Houston TX: Connexions: Rice University.
  5. ^ "View Technologies MIT Technology Licensing Office".
  6. ^ 고속 유한 푸리에 변환: MATLAB 6은 FFTW를 통합합니다.
  7. ^ "FFTW FAQ"

외부 링크