Algoritmo FFT de factor primo

ImprimirCitar

Fast Fourier Transform algoritmo

El algoritmo del factor primo (PFA), también llamado algoritmo Good-Thomas (1958/1963), es un algoritmo de transformada rápida de Fourier (FFT) que -expresa la transformada discreta de Fourier (DFT) de tamaño N = N₁N₂ como una DFT bidimensional N₁×N₂, pero solo para el caso donde N₁ y N₂ son primos relativos. Estas transformaciones más pequeñas de tamaño N₁ y N₂ se pueden evaluar aplicando PFA de forma recursiva o usando algunos otro algoritmo FFT.

PFA no debe confundirse con la generalización mixed-radix del popular algoritmo Cooley-Tukey, que también subdivide una DFT de tamaño N = N₁N₂ en transformadas más pequeñas de tamaño N₁ y N₂. El último algoritmo puede usar cualquier factor (no necesariamente primos relativamente), pero tiene la desventaja de que también requiere multiplicaciones adicionales por raíces de la unidad llamadas factores twiddle, además de las transformadas más pequeñas. Por otro lado, PFA tiene las desventajas de que solo funciona para factores relativamente primos (por ejemplo, es inútil para tamaños de potencia de dos) y que requiere una reindexación más complicada de los datos basada en los isomorfismos del grupo aditivo. Tenga en cuenta, sin embargo, que PFA se puede combinar con Cooley-Tukey de raíz mixta, con el primero factorizando N en componentes relativamente primos y el segundo manejando factores repetidos.

PFA también está estrechamente relacionado con el algoritmo FFT de Winograd anidado, donde este último realiza el descompuesto N₁ por N₂ transformar a través de técnicas de convolución bidimensionales más sofisticadas. Por lo tanto, algunos artículos más antiguos también llaman al algoritmo de Winograd PFA FFT.

(Aunque el PFA es distinto del algoritmo Cooley-Tukey, el trabajo de Good de 1958 sobre el PFA fue citado como inspiración por Cooley y Tukey en su artículo de 1965, e inicialmente hubo cierta confusión sobre si los dos algoritmos eran diferentes De hecho, fue el único trabajo anterior de FFT citado por ellos, ya que no estaban al tanto de la investigación anterior de Gauss y otros).

Algoritmo

Vamos $a(x)$ un polinomio y $omega _{n}$ a principal $n$ raíz de la unidad. Definimos el DFT $a(x)$ como $n$ -tuple ${displaystyle ({hat {a}}_{j})=(a(omega _{n}^{j}))}$ . En otras palabras,

{displaystyle {hat {a}}_{j}=sum _{i=0}^{n-1}a_{i}omega _{n}^{ij}}

para todos

{displaystyle j=0,1,dotsn-1}

Para la simplicidad, denotamos la transformación como ${displaystyle {text{DFT}}_{omega _{n}}}$ .

El PFA se basa en una factorización coprime ${displaystyle n=prod _{d=0}^{D-1}n_{d}}$ y vueltas ${displaystyle {text{DFT}}_{omega _{n}}}$ en ${displaystyle bigotimes _{d}{text{DFT}}_{omega _{n_{d}}}}$ para algunas opciones ${displaystyle omega _{n_{d}}}$ Donde $bigotimes$ es el producto tensor.

Mapeo basado en CRT

Para una factorización coprime ${displaystyle n=prod _{d=0}^{D-1}n_{d}}$ , tenemos el mapa de restos chinos ${displaystyle mmapsto (m{bmod {q}}_{d})}$ desde ${mathbb {Z}}_{{n}}$ a ${displaystyle prod _{d=0}^{D-1}mathbb {Z} _{n_{d}}}$ con ${displaystyle (m_{d})mapsto sum _{d=0}^{D-1}e_{d}m_{d}}$ como su inverso ${displaystyle e_{d}}$ 's son los elementos centrales ortogonales idempotent con ${displaystyle sum _{d=0}^{D-1}e_{d}=1{pmod {n}}}$ . Elegir ${displaystyle omega _{n_{d}}=omega _{n}^{e_{d}}}$ (por lo tanto, ${displaystyle prod _{d=0}^{D-1}omega _{n_{d}}=omega _{n}^{sum _{d=0}^{D-1}e_{d}}=omega _{n}}$ ), reescribimos ${displaystyle {text{DFT}}_{omega _{n}}}$ como sigue:

{displaystyle {hat {a}}_{j}=sum _{i=0}^{n-1}a_{i}omega _{n}^{ij}=sum _{i=0}^{n-1}a_{i}left(prod _{d=0}^{D-1}omega _{n_{d}}right)^{ij}=sum _{i=0}^{n-1}a_{i}prod _{d=0}^{D-1}omega _{n_{d}}^{(i{bmod {n}}_{d})(j{bmod {n}}_{d})}=sum _{i_{0}=0}^{n_{0}-1}cdots sum _{i_{D-1}}^{n_{D-1}-1}a_{sum _{d=0}^{D-1}e_{d}i_{d}}prod _{d=0}^{D-1}omega _{n_{d}}^{i_{d}(j{bmod {n}}_{d})}}

Finalmente, definir ${displaystyle a_{i_{0},dotsi_{D-1}}=a_{sum _{d=0}^{D-1}i_{d}e_{d}}}$ y ${displaystyle {hat {a}}_{j_{0},dotsj_{D-1}}={hat {a}}_{sum _{d=0}^{D-1}j_{d}e_{d}}}$ , tenemos ${displaystyle {hat {a}}_{j_{0},dotsj_{D-1}}=sum _{i_{0}=0}^{n_{0}-1}cdots sum _{i_{D-1}}^{n_{D-1}-1}a_{i_{0},dotsi_{D-1}}prod _{d=0}^{D-1}omega _{n_{d}}^{i_{d}j_{d}}}$ . Por lo tanto, tenemos el DFT multidimensional, ${displaystyle otimes _{d=0}^{D-1}{text{DFT}}_{omega _{n_{d}}}}$ .

Como isomorfismos de álgebra

PFA puede ser declarado de forma de alto nivel en términos de isomorfismos de álgebra. Primero recordamos que para un anillo conmutativo $R$ y un isomorfismo de grupo $G$ a ${displaystyle prod _{d}G_{d}}$ , tenemos el siguiente isomorfismo de álgebra

{displaystyle R[G]cong bigotimes _{d}R[G_{d}]}

Donde

bigotimes

se refiere al producto tensor de álgebras.

Para ver cómo funciona PFA, elegimos ${displaystyle G=(mathbb {Z} _{n},+,0)}$ y ${displaystyle G_{d}=(mathbb {Z} _{n_{d}},+,0)}$ ser grupos aditivos. También identificamos $R[G]$ como ${displaystyle {frac {R[x]}{langle x^{n}-1rangle }}}$ y ${displaystyle R[G_{d}]}$ como ${displaystyle {frac {R[x_{d}]}{langle x_{d}^{n_{d}}-1rangle }}}$ . Elegir ${displaystyle eta =amapsto (a{bmod {n}}_{d})}$ como el isomorfismo del grupo ${displaystyle Gcong prod _{d}G_{d}}$ , tenemos el isomorfismo álgebra ${displaystyle eta ^{*}:R[G]cong bigotimes _{d}R[G_{d}]}$ , o alternativamente, ${displaystyle eta ^{*}:{frac {R[x]}{langle x^{n}-1rangle }}cong bigotimes _{d}{frac {R[x_{d}]}{langle x_{d}^{n_{d}}-1rangle }}}$ . Ahora observen que ${displaystyle {text{DFT}}_{omega _{n}}}$ es en realidad un isomorfismo álgebra de ${displaystyle {frac {R[x]}{langle x^{n}-1rangle }}}$ a ${displaystyle prod _{i}{frac {R[x]}{langle x-omega _{n}^{i}rangle }}}$ y cada uno ${displaystyle {text{DFT}}_{omega _{n_{d}}}}$ es un isomorfismo álgebra de ${displaystyle {frac {R[x]}{langle {x_{d}}^{n_{d}}-1rangle }}}$ a ${displaystyle prod _{i_{d}}{frac {R[x_{d}]}{langle x_{d}-omega _{n_{d}}^{i_{d}}rangle }}}$ , tenemos un isomorfismo álgebra $eta '$ desde ${displaystyle bigotimes _{d}prod _{i_{d}}{frac {R[x_{d}]}{langle x_{d}-omega _{n_{d}}^{i_{d}}rangle }}}$ a ${displaystyle prod _{i}{frac {R[x]}{langle x-omega _{n}^{i}rangle }}}$ . Lo que PFA nos dice es que ${displaystyle {text{DFT}}_{omega _{n}}=eta 'circ bigotimes _{d}{text{DFT}}_{omega _{n_{d}}}circ eta ^{*}}$ Donde $eta ^{*}$ y $eta '$ están re-indexando sin aritmética real en $R$ .

Contar el número de transformaciones multidimensionales

Note que la condición para la transformación ${displaystyle {text{DFT}}_{omega _{n}}}$ en ${displaystyle eta 'circ bigotimes _{d}{text{DFT}}_{omega _{n_{d}}}circ eta ^{*}}$ depende del isomorfismo del grupo aditivo $eta$ desde ${displaystyle (mathbb {Z} _{n},+,0)}$ a ${displaystyle prod _{d}(mathbb {Z} _{n_{d}},+,0)}$ . Cualquier isomorfismo de grupo aditivo funcionará. Contar el número de formas de transformación ${displaystyle {text{DFT}}_{omega _{n}}}$ en ${displaystyle eta 'circ bigotimes _{d}{text{DFT}}_{omega _{n_{d}}}circ eta ^{*}}$ , sólo necesitamos contar el número de isomorfismos de grupo aditivo de ${displaystyle (mathbb {Z} _{n},+,0)}$ a ${displaystyle prod _{d}(mathbb {Z} _{n_{d}},+,0)}$ , o alternativa, el número de automorfismos de grupo aditivo en ${displaystyle (mathbb {Z} _{n},+,0)}$ . Desde ${displaystyle (mathbb {Z} _{n},+,0)}$ es cíclico, cualquier automorfismo puede ser escrito como ${displaystyle 1mapsto g}$ Donde $g$ es un generador de ${displaystyle (mathbb {Z} _{n},+,0)}$ . Por definición ${displaystyle (mathbb {Z} _{n},+,0)}$ , $g$ Son exactamente esos coprime $n$ . Por lo tanto, hay exactamente $varphi (n)$ muchos de esos mapas donde $varphi$ es la función totiente de Euler. El ejemplo más pequeño es $n = 6$ Donde ${displaystyle varphi (n)=2}$ , demostrando los dos mapas de la literatura: el "CRT mapping" y el "Ruritanian mapping".