El algoritmo de factor primo (PFA) , también llamado algoritmo de Good-Thomas (1958/1963), es un algoritmo de transformada de Fourier rápida (FFT) que reexpresa la transformada de Fourier discreta (DFT) de un tamaño N = N 1 N 2 como una DFT bidimensional de N 1 × N 2 , pero solo para el caso en el que N 1 y N 2 son primos relativos . Estas transformadas más pequeñas de tamaño N 1 y N 2A continuación, se puede evaluar aplicando PFA de forma recursiva o utilizando algún otro algoritmo FFT.
PFA no debe confundirse con la generalización de base mixta del popular algoritmo Cooley-Tukey , que también subdivide una DFT de tamaño N = N 1 N 2 en transformadas más pequeñas de tamaño N 1 y N 2 . El último algoritmo puede usar cualquier factor (no necesariamente primo relativo), pero tiene la desventaja de que también requiere multiplicaciones adicionales por raíces de unidad llamadas factores twiddle , además de las transformaciones más pequeñas. Por otro lado, PFA tiene las desventajas de que solo funciona para factores primos relativamente (por ejemplo, es inútil para potencias de dos tamaños) y que requiere una reindexación más complicada de los datos basada en el teorema del resto chino ( CRT). Sin embargo, tenga en cuenta que el PFA se puede combinar con Cooley-Tukey de radix mixtas, donde el primero factoriza N en componentes relativamente primos y el segundo maneja factores repetidos.
PFA también está estrechamente relacionado con el algoritmo Winograd FFT anidado , donde este último realiza la transformada N 1 por N 2 descompuesta a través de técnicas de convolución bidimensional 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 en 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 previo de FFT citado por ellos, ya que entonces no estaban al tanto de la investigación anterior de Gauss y otros).
Recuerde que la DFT se define mediante la fórmula:
El PFA implica una reindexación de las matrices de entrada y salida, que cuando se sustituyen en la fórmula DFT la transforma en dos DFT anidadas (una DFT bidimensional).
Re-indexación
Suponer que , dónde y son relativamente primos, es decir . Luego, la reindexación se realiza utilizando dos mapeos biyectivos entre y .
El primer mapa
es una biyección llamada mapeo ruritano (también mapeo de Good ).
De hecho es un homomorfismo , porque y :
Por tanto, de acuerdo con el primer teorema de isomorfismo ,es una inyección al grupo cociente . Aquí el kernel , porque de lo contrario existiría un par y , que no son simultáneamente cero, de modo que para algunos distintos de cero . Desde, el único valor restante de es 1. En este caso sería un número entero de lo cual es imposible, porque para la fracción para producir un valor integral, debe ser un múltiplo de (desde ). Pero esto contradeciría. Por lo tanto,, es decir inyecta a . Ahora desde, es de hecho biyectiva, es decir, para valores distintos del par produce distintos valores de a lo largo de todo el set .
El segundo mapa
se llama mapeo CRT . El nombre se refiere al teorema del resto chino que proporciona el mapeo biyectivo, en el cual y son cualquier solución a la ecuación lineal diofántica de la ecuación(ver identidad de Bézout ).
Para realizar la DFT, es necesario mapear diferentes pares de y a distintos valores de y tambien parejas y a . Para hacerlo, se puede usar el mapeo ruritano para producir índices en el vector de entrada y el mapeo CRT para evaluar los índices del vector de salida o usar los dos mapeos de manera opuesta.
Se ha dedicado una gran cantidad de investigación a los esquemas para evaluar esta reindexación de manera eficiente, idealmente en el lugar , mientras se minimiza el número de costosas operaciones de módulo (resto) (Chan, 1991 y referencias).
Reexpresión de DFT
La reindexación anterior se sustituye luego en la fórmula del DFT y, en particular, en el producto. en el exponente. Porque, este exponente se evalúa modulo . Similar, y son implícitamente periódicas en , por lo que sus subíndices se evalúan módulo .
Primero, sustituya el mapeo ruritano en la fórmula de DFT:
- .
Ahora sustituya el mapeo CRT en lugar de para producir
Asimismo, la sustitución del mapeo CRT en lugar de y mapeo ruritano en lugar de rendimientos
- .
En ambos casos, las sumas internas y externas son simplemente DFT de tamaño y , respectivamente.