6.4: Teoremas de la complejidad de Winograd

Debido a que el trabajo de Winograd ha sido la base de los resultados modernos en algoritmos de convolución eficiente y DFT, vale la pena mirar sus conclusiones teóricas sobre algoritmos óptimos. La mayoría de sus resultados son declarados en términos de multiplicación polinómica como Descripción polinómica de señales. La medida de la complejidad computacional suele ser el número de multiplicaciones, y solo se cuentan ciertas multiplicaciones. Esto debe entenderse para no malinterpretar los resultados.

Esta sección simplemente dará una declaración de los resultados pertinentes y no intentará derivar ni probar nada. Se dará una breve interpretación de cada teorema para relacionar el resultado con los algoritmos desarrollados en este capítulo. Las referencias indicadas deben ser consultadas para antecedentes y detalles.

Teorema 1

Dados dos polinomios,\(x(s)\) y\(h(s)\), de grado\(N\) y\(M\) respectivamente, cada uno con coeficientes indeterminados que son elementos de un campo\(H\),\(N+M+1\) las multiplicaciones son necesarias para calcular los coeficientes del polinomio producto\(x(s)h(s)\). La multiplicación por elementos del campo\(G\) (el campo de constantes), que está contenida en\(H\), no se cuenta y\(G\) contiene al menos elementos\(N+M\) distintos.

El límite superior en este teorema se puede realizar eligiendo un polinomio de módulo arbitrario\(P(s)\) de grado\(N+M+1\) compuesto por\(N+M+1\) distintos factores polinómicos lineales con coeficientes en los\(G\) que, al ser su grado mayor que el producto\(x(s)h(s)\), no tenga efecto sobre el producto, y al reducir\(x(s)\) y\(h(s)\) a\(N+M+1\) los residuos módulo los\(N+M+1\) factores de\(P(s)\). Estos residuos se multiplican entre sí, requiriendo\(N+M+1\) multiplicaciones, y los resultados se recombinan usando el teorema del resto chino (TRC). No se cuentan las operaciones requeridas en la reducción y recombinación, mientras que las multiplicaciones de residuos son. Dado que el módulo\(P(s)\) es arbitrario, sus factores se eligen para que sean simples para que la reducción y la TRC sean simples. Los factores de cero, más y menos unidad, e infinito son los más simples. Más y menos dos y otros factores complican considerablemente los cálculos reales, pero el teorema no toma eso en cuenta. Este algoritmo es una forma del algoritmo Toom-Cook y de interpolación Lagrange. Para nuestras aplicaciones,\(H\) es el campo de los reales y\(G\) el campo de los racionales.

Teorema 2

Si existe un algoritmo que calcula\(x(s)h(s)\) en\(N+M+1\) multiplicaciones, todos menos uno de sus pasos de multiplicación deben ser necesariamente de la forma

\[mk=(gk'+xg(k))(gk''+hg(k))\; \; for\; \; k=0,1,...,N+M \nonumber \]

donde\(g_k\) son elementos distintos de\(G\);\(g_k'\) y\(g_k''\) son elementos arbitrarios de\(G\).

Este teorema afirma que la estructura de un algoritmo óptimo es esencialmente única aunque los factores de\(P(s)\) pueden elegirse arbitrariamente.

Teorema 3

Dejar\(P(s)\) ser un polinomio de grado\(N\) y ser de la forma\(P(s)=Q(s)k\), donde\(Q(s)\) es un polinomio irreducible con coeficientes en\(G\) y\(k\) es un entero positivo. Dejar\(x(s)\) y\(h(s)\) ser dos polinomios de grado al menos\(N-1\) con coeficientes de\(H\), entonces se requieren\(2N-1\) multiplicaciones para computar el\(x(s)h(s)\) módulo producto\(P(s)\).

Este teorema es similar al Teorema 1 con las operaciones de la reducción del módulo producto\(P(s)\) no siendo contabilizadas.

Teorema 4

Cualquier algoritmo que calcule el\(x(s)h(s)\) módulo producto de\(P(s)\) acuerdo con las condiciones establecidas en el Teorema 3 y requiera\(2N-1\) multiplicaciones será necesariamente de una de tres estructuras, cada una de las cuales tiene la forma del Teorema 2 internamente.

Al igual que en el Teorema 2, este teorema afirma que solo existe un número limitado de estructuras posibles para algoritmos óptimos.

Teorema 5

Si el polinomio módulo\(P(s)\) tiene grado\(N\) y no es irreducible, se puede escribir en una forma factorizada única

\[P(s)=P_{1}^{m_{1}}(s)P_{2}^{m_{2}}(s)...P_{k}^{m_{k}}(s) \nonumber \]

donde cada uno de los\(P_i(s)\) son irreducibles sobre el campo de coeficiente permitido\(G\). \(2N-k\)las multiplicaciones son necesarias para calcular el\(x(s)h(s)\) módulo del producto\(P(s)\) donde\(x(s)\) y\(h(s)\) tienen coeficientes en\(H\) y son de grado al menos\(N-1\). Todos los algoritmos que calculen este producto en\(2N-k\) multiplicaciones deben ser de una forma donde cada uno de los polinomios de k residuos de\(x(s)\) y\(h(s)\) se multipliquen por separado modulo los factores de\(P(s)\) vía el CRT.

Corolario

Si el polinomio módulo es\(P(s)=s^{N}-1\) entonces\(2N-t(N)\) las multiplicaciones son necesarias para calcular\(x(s)h(s)\) módulo\(P(s)\), donde\(t(N)\) está el número de divisores positivos de\(N\).

El teorema 5 es muy general ya que permite un polinomio de módulo general. La prueba del límite superior implica reducir\(x(s)\) y\(h(s)\) módulo los\(k\) factores de\(P(s)\). Cada uno de los polinomios de residuos\(k\) irreducibles se multiplica luego usando el método del Teorema 4 requiriendo\(2Ni-1\) multiplica y los productos se combinan usando el CRT. El número total de multiplica de las\(k\) partes es\(2n-k\). El teorema también afirma que la estructura de estos algoritmos óptimos es esencialmente única. El caso especial de\(P(s)=s^{N}-1\) es interesante ya que corresponde a convolución cíclica y, como se afirma en el corolario,\(k\) se determina fácilmente. Los factores de\(s^N-1\) se denominan polinomios ciclotómicos y tienen propiedades interesantes.

Teorema 6

Considera calcular la DFT de una secuencia numérica de valor real de longitud prima. Si\(G\) se elige como campo de números racionales, el número de multiplicaciones reales necesarias para calcular una longitud-\(P\) DFT es

\[u(DFT(N))=2P-3-t(P-1)\; \; where\; \; t(P-1)\; is\; the\; number\; of\; divisors\; of\; P-1 \nonumber \]

Este teorema no solo da un límite inferior en cualquier algoritmo práctico de DFT de longitud prima, sino que también da algoritmos prácticos para\(N=3,5,\: \text{and}\: 7\). Considera los recuentos de operaciones en la Tabla para entender este teorema. Además de las multiplicaciones reales contadas por la teoría de la complejidad, cada algoritmo de longitud de inicialización óptima tendrá una multiplicación por una constante racional. Esa constante corresponde al residuo módulo (\(s-1\)) que siempre existe para el módulo\(P(s)=s^{N}-1\). En un algoritmo práctico, esta multiplicación debe llevarse a cabo, y que da cuenta de la diferencia en la predicción del Teorema 6 y el conteo en la Tabla. Además, existe otra operación que para ciertas aplicaciones se debe contar como una multiplicación. Ese es el cálculo del término de frecuencia cero\(X(0)\) en la primera fila del ejemplo en La DFT como Convolución o Filtrado. Para las aplicaciones al WFTA discutidas en The Prime Factor y Winograd Fourier Transform Algorithms, esa operación debe ser contada como una multiplicación. Para longitudes más largas que\(7\), los algoritmos óptimos requieren demasiadas adiciones, por lo que se utilizan estructuras de compromiso.

Teorema 7

Si\(G\) se elige como el campo de números racionales, el número de multiplicaciones reales necesarias para calcular una longitud-\(N\) DFT donde\(N\) es un número primo elevado a una potencia entera:\(N=Pm\), viene dada por

\[u(DFT(N))=2N-((m2+m)/2)t(P-1)-m-1 \nonumber \]

donde\(t(P-1)\) es el número de divisores de (\(P-1\)).

Este resultado parece ser prácticamente alcanzable sólo para\(N=9\), o tal vez\(25\). En el caso de\(N=9\), hay dos multiplicaciones racionales que deben llevarse a cabo y se cuentan en la Tabla pero no son pronosticadas por el Teorema 7. La experiencia indica que incluso para\(N=25\), un algoritmo basado en una FFT de Cooley-Tukey usando un mapa de índice de tipo 2 da un resultado más equilibrado en general.

Teorema 8

Si\(G\) se elige como campo de números racionales, el número de multiplicaciones reales necesarias para calcular una longitud-\(N\) DFT donde\(N=2m\) viene dada por

\[u(DFT(N))=2N-m2-m-2 \nonumber \]

Este resultado no es prácticamente útil porque el número de adiciones necesarias para realizar este mínimo de multiplicaciones se vuelve muy grande para longitudes mayores que\(16\). Sin embargo, demuestra que el número mínimo de multiplicaciones requeridas de un algoritmo óptimo es una función lineal\(N\) más que de la\(N\log N\) que se requiere de algoritmos prácticos. El mejor algoritmo práctico de potencia de dos parece a la FFT Split-Radix discutida en The Cooley-Tukey Fast Fourier Transform Algorithm.

Todos estos teoremas utilizan ideas basadas en la reducción de residuos, la multiplicación de los residuos, y luego la combinación por el CRT. Es notable que este enfoque encuentre el número mínimo de multiplicaciones requeridas por una prueba constructiva que genera un algoritmo que logra este mínimo; y la estructura del algoritmo óptimo es, dentro de ciertas variaciones, única. Para longitudes más cortas, los algoritmos óptimos dan programas prácticos. Para longitudes más largas, las operaciones no contadas involucradas con la multiplicación de los polinomios de residuos de mayor grado se vuelven muy grandes y poco prácticas. En esos casos, se pueden generar algoritmos subóptimos eficientes utilizando la misma reducción de residuos que para el caso óptimo, pero utilizando métodos distintos del algoritmo Toom-Cook del Teorema 1 para multiplicar los polinomios de residuos.

Los algoritmos prácticos de DFT largos se producen combinando DFT óptimos de longitud corta con el mapa de índice Tipo 1 del Mapeo de Índice Multidimensional para dar el Algoritmo de Factor Primo (PFA) y el Algoritmo de Transformada de Fourier de Winograd (WFTA) discutidos en The Prime Factor y Winograd Fourier Transform Algoritmos. Es interesante señalar que la técnica de mapeo de índices es útil dentro de los algoritmos de DFT cortos para reemplazar el algoritmo Toom-Cook y afuera para combinar los DFT cortos para calcular DFT largos.

Colaborador

• ContribeeBurrus