Convolution, transformée de Fourier rapide et polynômes (2022)

Polynômes, transformée de Fourier rapide et convolution

Polynômes : résumé rapide

• Un polynôme (P(x)) est une somme de termes, chacun composé de la variable (x), d’un exposant (k) et d’un coefficient (a_k)
• Exemple : (P(x) = 5x^2 + 2x + 9)
• Additionner ou soustraire deux polynômes (P(x)) et (Q(x)) consiste à additionner ou soustraire chaque terme individuellement
• Exemple de code Python :

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

Convolution

• La convolution est la composition de deux signaux (p) et (q)
• Exemple : (p = [2, 3, 4]), (q = [5, 6, 7])
• Calcul de la convolution :

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

• La multiplication de polynômes peut être exprimée comme une convolution

Transformée de Fourier et FFT

• La transformée de Fourier est un outil puissant pour convertir un signal du domaine temporel vers le domaine fréquentiel
• Différences entre la transformée de Fourier (FT), la transformée de Fourier discrète (DFT) et la transformée de Fourier rapide (FFT) :
  • FT : transformée de Fourier pour les signaux continus
  • DFT : transformée de Fourier pour les signaux discrets
  • FFT : algorithme permettant de calculer efficacement la DFT ((O(n \log n)))

Accélérer la multiplication de polynômes

• La multiplication de polynômes apprise au lycée a une complexité en (O(n^2))
• Méthode plus efficace :
  1. Convertir les polynômes dans le domaine fréquentiel ((O(n \log n)))
  2. Effectuer la multiplication dans le domaine fréquentiel ((O(n)))
  3. Reconvertir le résultat dans le domaine temporel ((O(n \log n)))
• Exemple de code 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()
  

Résumé

• La méthode de base pour multiplier des polynômes a une complexité en (O(n^2))
• La multiplication de polynômes peut être exprimée comme une convolution
• La convolution dans le domaine temporel est équivalente à la multiplication dans le domaine fréquentiel
• En utilisant la FFT pour convertir les polynômes dans le domaine fréquentiel, on peut les multiplier avec une complexité en (O(n \log n))

L’avis de GN⁺

• Cet article explique comment améliorer l’efficacité de la multiplication de polynômes, en soulignant notamment l’importance de la transformée de Fourier rapide (FFT)
• Il montre qu’elle est bien plus efficace que la méthode de base apprise au lycée
• Cette technique peut être utile dans de nombreux domaines, notamment le traitement du signal et le traitement d’image
• Avec la FFT, il est possible d’effectuer rapidement la multiplication de grands polynômes, ce qui est avantageux pour le traitement de données à grande échelle
• D’autres projets offrant des fonctionnalités similaires incluent notamment NumPy et SciPy