Algorytm FFT z czynnikiem pierwszym

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

Algorytm

Niech \ jedności wielomian i główny } Definiujemy DFT z jako jako ) . Innymi słowy,

dla wszystkich .

Dla uproszczenia oznaczamy transformację jako .

PFA opiera się na faktoryzacji względnie pierwszej i { into for some choices of 's where jest iloczynem .

Mapowanie oparte na CRT

rozkładu mapę _ od do re d środkową ortogonalną elementy idempotentne z } Wybór (dlatego ), przepisujemy w następujący sposób:

.

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

gdzie odnosi do tensorowego algebr .

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”

Zobacz też

  •    Dobrze, IJ (1958). „Algorytm interakcji i praktyczna analiza Fouriera”. Journal of Royal Statistical Society, seria B. 20 (2): 361–372. JSTOR 2983896 . Dodatek, ibid. 22 (2), 373-375 (1960) JSTOR 2984108 .
  • Thomas, LH (1963). „Wykorzystanie komputera do rozwiązywania problemów z fizyki”. Zastosowania komputerów cyfrowych . Boston: Gin.
  • Duhamel, P.; Vetterli, M. (1990). „Szybkie transformacje Fouriera: przegląd samouczka i stan wiedzy” . Przetwarzanie sygnału . 19 (4): 259–299. doi : 10.1016/0165-1684(90)90158-U .
  • Chan, Karolina Południowa; Ho, KL (1991). „O indeksowaniu algorytmu szybkiej transformaty Fouriera z czynnikiem pierwszym”. IEEE Trans. Obwody i systemy . 38 (8): 951–953. doi : 10.1109/31.85638 .
  • Dobrze, IJ (1971). „Zależność między dwoma szybkimi transformatami Fouriera”. Transakcje IEEE na komputerach . 100 (3): 310–317.