Faltung, schnelle Fourier-Transformation und Polynome (2022)

Polynome, schnelle Fourier-Transformation und Faltung

Polynome: eine kurze Zusammenfassung

• Ein Polynom (P(x)) ist die Summe von Termen, bei denen jeder Term aus der Variablen (x), einem Exponenten (k) und einem Koeffizienten (a_k) besteht
• Beispiel: (P(x) = 5x^2 + 2x + 9)
• Zwei Polynome (P(x)) und (Q(x)) zu addieren oder zu subtrahieren bedeutet, die jeweiligen Terme einzeln zu addieren oder zu subtrahieren
• Python-Codebeispiel:

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

Faltung

• Faltung ist die Zusammensetzung zweier Signale (p) und (q)
• Beispiel: (p = [2, 3, 4]), (q = [5, 6, 7])
• Berechnung der Faltung:

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

• Polynom-Multiplikation kann als Faltung dargestellt werden

Fourier-Transformation und FFT

• Die Fourier-Transformation ist ein leistungsstarkes Werkzeug, um Signale vom Zeitbereich in den Frequenzbereich zu transformieren
• Unterschiede zwischen Fourier-Transformation (FT), diskreter Fourier-Transformation (DFT) und schneller Fourier-Transformation (FFT):
  • FT: Fourier-Transformation für kontinuierliche Signale
  • DFT: Fourier-Transformation für diskrete Signale
  • FFT: ein Algorithmus zur effizienten Berechnung der DFT ((O(n \log n)))

Polynom-Multiplikation beschleunigen

• Die in der Schule gelernte Polynom-Multiplikation hat eine Komplexität von (O(n^2))
• Ein effizienterer Ansatz:
  1. Polynome in den Frequenzbereich transformieren ((O(n \log n)))
  2. Multiplikation im Frequenzbereich ausführen ((O(n)))
  3. Das Ergebnis zurück in den Zeitbereich transformieren ((O(n \log n)))
• Python-Codebeispiel:

  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()
  

Zusammenfassung

• Die grundlegende Methode der Polynom-Multiplikation hat eine Komplexität von (O(n^2))
• Polynom-Multiplikation kann als Faltung dargestellt werden
• Faltung im Zeitbereich entspricht Multiplikation im Frequenzbereich
• Mit FFT lassen sich Polynome in den Frequenzbereich transformieren, sodass sie mit einer Komplexität von (O(n \log n)) multipliziert werden können

Meinung von GN⁺

• Dieser Artikel erklärt, wie sich die Effizienz der Polynom-Multiplikation steigern lässt, und betont insbesondere die Bedeutung der schnellen Fourier-Transformation (FFT)
• Er zeigt, dass sie deutlich effizienter ist als die grundlegende Methode, die man in der Schule lernt
• Diese Technik kann in vielen Bereichen nützlich eingesetzt werden, etwa in der Signalverarbeitung und Bildverarbeitung
• Mit FFT lässt sich die Multiplikation großer Polynome schnell ausführen, was bei der Verarbeitung großer Datenmengen von Vorteil ist
• Ähnliche Projekte mit vergleichbarer Funktionalität sind unter anderem NumPy und SciPy