Konvolüsyon, Hızlı Fourier Dönüşümü ve Polinomlar (2022)

Polinomlar, Hızlı Fourier Dönüşümü ve Konvolüsyon

Polinomlar: Kısa bir özet

• Bir polinom (P(x)), her terimi değişken (x), üs (k) ve katsayı (a_k) ile oluşturulan terimlerin toplamıdır
• Örnek: (P(x) = 5x^2 + 2x + 9)
• İki polinomu, (P(x)) ve (Q(x)), toplamak veya çıkarmak, her terimi ayrı ayrı toplamak ya da çıkarmak anlamına gelir
• Python kod örneği:

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

Konvolüsyon

• Konvolüsyon, iki sinyal (p) ve (q)'nun bileşimidir
• Örnek: (p = [2, 3, 4]), (q = [5, 6, 7])
• Konvolüsyon hesabı:

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

• Polinom çarpımı, konvolüsyon olarak ifade edilebilir

Fourier dönüşümü ve FFT

• Fourier dönüşümü, sinyalleri zaman alanından frekans alanına dönüştüren güçlü bir araçtır
• Fourier dönüşümü (FT), ayrık Fourier dönüşümü (DFT) ve hızlı Fourier dönüşümü (FFT) arasındaki farklar:
  • FT: Sürekli sinyaller için Fourier dönüşümü
  • DFT: Ayrık sinyaller için Fourier dönüşümü
  • FFT: DFT'yi verimli biçimde hesaplayan algoritma ((O(n \log n)))

Polinom çarpımını daha hızlı yapmak

• Lisede öğrendiğimiz polinom çarpımı (O(n^2)) karmaşıklığına sahiptir
• Daha verimli yöntem:
  1. Polinomları frekans alanına dönüştürme ((O(n \log n)))
  2. Frekans alanında çarpma işlemini gerçekleştirme ((O(n)))
  3. Sonucu yeniden zaman alanına dönüştürme ((O(n \log n)))
• Python kod örneği:

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

Özet

• Polinom çarpımının temel yöntemi (O(n^2)) karmaşıklığına sahiptir
• Polinom çarpımı, konvolüsyon olarak ifade edilebilir
• Zaman alanındaki konvolüsyon, frekans alanındaki çarpma ile aynıdır
• FFT kullanılarak polinomlar frekans alanına dönüştürüldüğünde, polinomlar (O(n \log n)) karmaşıklıkla çarpılabilir

GN⁺ görüşü

• Bu yazı, polinom çarpımının verimliliğini artırma yöntemlerini açıklıyor ve özellikle hızlı Fourier dönüşümünün (FFT) önemini vurguluyor
• Lisede öğrenilen temel yöntemden çok daha verimli olduğunu gösteriyor
• Bu teknik, sinyal işleme, görüntü işleme gibi çeşitli alanlarda faydalı biçimde kullanılabilir
• FFT kullanıldığında büyük polinomların çarpımı hızlıca gerçekleştirilebilir; bu da büyük ölçekli veri işleme için avantaj sağlar
• Benzer işlevlere sahip diğer projeler arasında NumPy ve SciPy bulunuyor