Convolución, transformada rápida de Fourier y polinomios (2022)

Polinomios, transformada rápida de Fourier y convolución

Polinomios: resumen rápido

• Un polinomio (P(x)) es una suma de términos, donde cada término está compuesto por una variable (x), un exponente (k) y un coeficiente (a_k)
• Ejemplo: (P(x) = 5x^2 + 2x + 9)
• Sumar o restar dos polinomios (P(x)) y (Q(x)) consiste en sumar o restar cada término por separado
• Ejemplo de código en Python:

  # a + b
  [a + b for a, b in zip(p, q)]
  # a - b
  [a - b for a, b in zip(p, q)]
  

Convolución

• La convolución es la combinación de dos señales (p) y (q)
• Ejemplo: (p = [2, 3, 4]), (q = [5, 6, 7])
• Cálculo de la convolución:

  y = [10, 27, 52, 45, 28]
  

• La multiplicación de polinomios puede expresarse como una convolución

Transformada de Fourier y FFT

• La transformada de Fourier es una herramienta poderosa para convertir señales del dominio del tiempo al dominio de la frecuencia
• Diferencias entre transformada de Fourier (FT), transformada discreta de Fourier (DFT) y transformada rápida de Fourier (FFT):
  • FT: transformada de Fourier para señales continuas
  • DFT: transformada de Fourier para señales discretas
  • FFT: algoritmo para calcular la DFT de forma eficiente ((O(n \log n)))

Multiplicar polinomios más rápido

• La multiplicación de polinomios que se aprende en la escuela tiene una complejidad de (O(n^2))
• Un método más eficiente:
  1. Convertir los polinomios al dominio de la frecuencia ((O(n \log n)))
  2. Multiplicar en el dominio de la frecuencia ((O(n)))
  3. Convertir el resultado de vuelta al dominio del tiempo ((O(n \log n)))
• Ejemplo de código en Python:

  def multiply_naive(p, q):
      result_size = len(p) + len(q) - 1
      result = [0] * result_size
      for i in range(len(p)):
          for j in range(len(q)):
              result[i + j] += p[i] * q[j]
      return result
  
  def multiply_fft(p, q):
      length = 2 ** np.ceil(np.log2(len(p) + len(q) - 1)).astype(int)
      f_padded = np.pad(p, (0, length - len(p)))
      g_padded = np.pad(q, (0, length - len(q)))
      Y = np.fft.fft(f_padded) * np.fft.fft(g_padded)
      result_coefficients = np.round(np.fft.ifft(Y).real).astype(int)
      return np.trim_zeros(result_coefficients, 'b').tolist()
  

Resumen

• El método básico para multiplicar polinomios tiene complejidad (O(n^2))
• La multiplicación de polinomios puede expresarse como una convolución
• La convolución en el dominio del tiempo es equivalente a la multiplicación en el dominio de la frecuencia
• Si se usa FFT para convertir polinomios al dominio de la frecuencia, se pueden multiplicar con complejidad (O(n \log n))

La opinión de GN⁺

• Este artículo explica cómo mejorar la eficiencia de la multiplicación de polinomios y destaca especialmente la importancia de la transformada rápida de Fourier (FFT)
• Muestra que es mucho más eficiente que el método básico aprendido en la escuela
• Esta técnica puede ser útil en varios campos, como procesamiento de señales y procesamiento de imágenes
• Usar FFT permite realizar rápidamente la multiplicación de polinomios grandes, lo que es ventajoso para el procesamiento de datos a gran escala
• Otros proyectos con funciones similares incluyen NumPy y SciPy