Кіріспе
Дискретті Фурье түрлендірмесін есептеуге арналған бағдарламалық кітапхана. Батыстағы ең жылдам Фурье түрлендірмесі (FFTW) – Массачусетс технология институтында Маттео Фриго және Стивен Г. Джонсон жасаған дискретті Фурье түрлендірмесін (DFT) есептеуге арналған бағдарламалық кітапхана. FFTW – жылдам Фурье түрлендіруінің (FFT) ең жылдам ашық кодты бағдарламалық қамтамасының бірі. Ол нақты және кешенді мәнді, кез келген өлшем мен өлшемдегі массивтер үшін FFT алгоритмін іске асырады.
The Fastest Fourier Transform in the West (FFTW) is a software library for computing discrete Fourier transforms (DFTs) developed by Matteo Frigo and Steven G. Johnson at the Massachusetts Institute of Technology. FFTW is one of the fastest free software implementations of the fast Fourier transform (FFT). It implements the FFT algorithm for real and complex valued arrays of arbitrary size and dimension.
Кітапхана
FFTW деректерді әртүрлі алгоритмдерді қолдау арқылы жылдам түрлендіреді және нақты жағдайда ең қолайлы деп бағалайтын немесе өлшейтін (трансформацияны кішірек трансформацияларға бөлу) алгоритмді таңдайды. Ол кішкентай жай сандарға ие массивтерде жақсы жұмыс істейді, екінің дәрежелері ең оңтайлы, ал үлкен жай сандар ең нашар жағдайды құрайды (бірақ бәрібір O(n log n) болып табылады). Құрама өлшемдердің трансформацияларын кішірек трансформацияларға бөлу үшін ол Кули-Туки FFT алгоритмінің бірнеше нұсқаларын таңдайды (әртүрлі факторлауларға және/немесе әртүрлі жадқа қол жеткізу үлгілеріне сәйкес), ал жай өлшемдер үшін Радер немесе Блюштейн FFT алгоритмін пайдаланады. Сондай-ақ, FFT есептеу үшін коммерциялық MATLAB матрицалық пакетінде қолданылады. FFTW C тілінде жазылған, бірақ Fortran және Ada интерфейстері де бар, сондай-ақ басқа бірнеше тілдер үшін де интерфейстер бар. Кітапхананың өзі C тілінде болғанымен, код OCaml тілінде жазылған 'genfft' деп аталатын бағдарламадан жасалады. 1999 жылы FFTW сандық бағдарламалық қамтамасыз ету саласындағы J. H. Wilkinson сыйлығына ие болды.