Algorytm czynników pierwszych (PFA) , zwany także algorytmem Gooda – Thomasa (1958/1963), jest algorytmem szybkiej transformaty Fouriera (FFT), który ponownie wyraża dyskretną transformatę Fouriera (DFT) o rozmiarze N = N 1 N 2 jako dwuwymiarowy N 1 × N 2 DFT, ale tylko dla przypadku, gdy N 1 i N 2 są względnie pierwsze . Te mniejsze transformaty o rozmiarach N1 i N2 można następnie ocenić, stosując rekurencyjnie PFA lub stosując inny algorytm FFT.
PFA nie należy mylić z uogólnieniem popularnego algorytmu Cooleya-Tukeya z mieszaną podstawą , który również dzieli DFT o rozmiarze N = N 1 N 2 na mniejsze transformaty o rozmiarach N 1 i N 2 . Ten ostatni algorytm może wykorzystywać dowolne czynniki (niekoniecznie względnie pierwsze), ale ma tę wadę, że wymaga również dodatkowych mnożeń przez pierwiastki jedności, zwanych współczynnikami twiddle , oprócz mniejszych przekształceń. Z drugiej strony PFA ma tę wadę, że działa tylko dla czynników względnie pierwszych (np. jest bezużyteczny w przypadku potęgi dwóch wielkości) i wymaga bardziej skomplikowanego ponownego indeksowania danych w oparciu o izomorfizmy grup addytywnych . Należy jednak zauważyć, że PFA można połączyć z mieszaną podstawą Cooleya-Tukeya, przy czym ten pierwszy rozkłada N na czynniki na stosunkowo pierwsze składniki, a drugi obsługuje powtarzające się czynniki.
PFA jest również ściśle powiązany z zagnieżdżonym algorytmem FFT Winograda, w którym ten ostatni wykonuje rozłożoną transformację N1 na N2 za pomocą bardziej wyrafinowanych technik splotu dwuwymiarowego . Dlatego w niektórych starszych artykułach algorytm Winograda nazywa się również PFA FFT.
(Chociaż PFA różni się od algorytmu Cooleya-Tukeya, praca Gooda z 1958 r. na temat PFA została przytoczona jako inspiracja przez Cooleya i Tukeya w ich artykule z 1965 r. i początkowo istniało pewne zamieszanie co do tego, czy te dwa algorytmy są różne. W rzeczywistości była to jedyna wcześniejsza praca FFT przez nich cytowana, ponieważ nie byli wówczas świadomi wcześniejszych badań Gaussa i innych).
Na koniec zdefiniuj i mamy za . Dlatego mamy wielowymiarowy DFT, .
Jako izomorfizmy algebry
PFA można określić w sposób ogólny w kategoriach izomorfizmów algebry . Najpierw pamiętamy, że dla pierścienia przemiennego izomorfizmu grupowego od do mamy następującą algebrę izomorfizm
Aby zobaczyć, jak działa PFA, wybieramy i G. be additive groups.
We also identify as i jako . Wybór jako izomorfizm grupy , mamy izomorfizm algebry lub alternatywnie . Teraz DFT rzeczywistości izomorfizmem algebry z do i każdy jest izomorfizmem algebry z do mamy izomorfizm algebry od do . PFA mówi nam, że gdzie i i są ponownie indeksowane bez rzeczywistej arytmetyki w .
Liczenie liczby transformacji wielowymiarowych
η ∘ displaystyle eta do . Każdy izomorfizm grupy addytywnej będzie działał. sposobów przekształca w liczbę izomorfizmów grup dodatków od do lub alternatywnie, liczba addytywnych automorfizmów grup na . Ponieważ jest cykliczny , każdy automorfizm można zapisać jako } jest ) } . z definicją, dokładnie takie, które są . istnieje dokładnie takich map w których funkcją Najmniejszym przykładem jest gdzie , demonstrując dwie mapy w literaturze: „mapowanie CRT” i „mapowanie Rurytanii”