Konvolusi, Transformasi Fourier Cepat, dan Polinomial (2022)

Polinomial, Transformasi Fourier Cepat, dan Konvolusi

Polinomial: ringkasan singkat

• Polinomial (P(x)) adalah penjumlahan suku-suku yang masing-masing terdiri dari variabel (x), pangkat (k), dan koefisien (a_k)
• Contoh: (P(x) = 5x^2 + 2x + 9)
• Menjumlahkan atau mengurangkan dua polinomial (P(x)) dan (Q(x)) berarti menjumlahkan atau mengurangkan setiap suku secara terpisah
• Contoh kode Python:

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

Konvolusi

• Konvolusi adalah penggabungan dua sinyal (p) dan (q)
• Contoh: (p = [2, 3, 4]), (q = [5, 6, 7])
• Perhitungan konvolusi:

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

• Perkalian polinomial dapat dinyatakan sebagai konvolusi

Transformasi Fourier dan FFT

• Transformasi Fourier adalah alat yang kuat untuk mengubah sinyal dari domain waktu ke domain frekuensi
• Perbedaan antara transformasi Fourier (FT), transformasi Fourier diskret (DFT), dan transformasi Fourier cepat (FFT):
  • FT: transformasi Fourier untuk sinyal kontinu
  • DFT: transformasi Fourier untuk sinyal diskret
  • FFT: algoritma untuk menghitung DFT secara efisien ((O(n \log n)))

Mempercepat perkalian polinomial

• Perkalian polinomial yang dipelajari di sekolah menengah memiliki kompleksitas (O(n^2))
• Metode yang lebih efisien:
  1. Ubah polinomial ke domain frekuensi ((O(n \log n)))
  2. Lakukan perkalian di domain frekuensi ((O(n)))
  3. Ubah kembali hasilnya ke domain waktu ((O(n \log n)))
• Contoh kode 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()
  

Ringkasan

• Metode dasar perkalian polinomial memiliki kompleksitas (O(n^2))
• Perkalian polinomial dapat dinyatakan sebagai konvolusi
• Konvolusi di domain waktu setara dengan perkalian di domain frekuensi
• Dengan menggunakan FFT untuk mengubah polinomial ke domain frekuensi, polinomial dapat dikalikan dengan kompleksitas (O(n \log n))

Opini GN⁺

• Tulisan ini menjelaskan cara meningkatkan efisiensi perkalian polinomial, khususnya dengan menekankan pentingnya transformasi Fourier cepat (FFT)
• Menunjukkan bahwa metode ini jauh lebih efisien daripada metode dasar yang dipelajari di sekolah menengah
• Teknik ini dapat digunakan secara berguna di berbagai bidang seperti pemrosesan sinyal dan pemrosesan citra
• Dengan FFT, perkalian polinomial besar dapat dilakukan dengan cepat, sehingga menguntungkan untuk pemrosesan data skala besar
• Proyek lain dengan fungsi serupa antara lain NumPy dan SciPy