Tích chập, biến đổi Fourier nhanh và đa thức (2022)

Đa thức, biến đổi Fourier nhanh và tích chập

Đa thức: tóm tắt ngắn gọn

• Đa thức (P(x)) là tổng của các hạng tử, trong đó mỗi hạng tử được tạo thành từ biến (x), số mũ (k) và hệ số (a_k)
• Ví dụ: (P(x) = 5x^2 + 2x + 9)
• Việc cộng hoặc trừ hai đa thức (P(x)) và (Q(x)) là cộng hoặc trừ từng hạng tử tương ứng
• Ví dụ mã Python:

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

Tích chập

• Tích chập là sự tổng hợp của hai tín hiệu (p) và (q)
• Ví dụ: (p = [2, 3, 4]), (q = [5, 6, 7])
• Tính tích chập:

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

• Phép nhân đa thức có thể được biểu diễn bằng tích chập

Biến đổi Fourier và FFT

• Biến đổi Fourier là một công cụ mạnh để chuyển đổi tín hiệu từ miền thời gian sang miền tần số
• Sự khác nhau giữa biến đổi Fourier (FT), biến đổi Fourier rời rạc (DFT) và biến đổi Fourier nhanh (FFT):
  • FT: biến đổi Fourier cho tín hiệu liên tục
  • DFT: biến đổi Fourier cho tín hiệu rời rạc
  • FFT: thuật toán tính DFT một cách hiệu quả ((O(n \log n)))

Tăng tốc phép nhân đa thức

• Phép nhân đa thức học ở cấp ba có độ phức tạp (O(n^2))
• Cách hiệu quả hơn:
  1. Chuyển đa thức sang miền tần số ((O(n \log n)))
  2. Thực hiện phép nhân trong miền tần số ((O(n)))
  3. Chuyển kết quả trở lại miền thời gian ((O(n \log n)))
• Ví dụ mã 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()
  

Tóm tắt

• Cách cơ bản để nhân đa thức có độ phức tạp (O(n^2))
• Phép nhân đa thức có thể được biểu diễn bằng tích chập
• Tích chập trong miền thời gian tương đương với phép nhân trong miền tần số
• Dùng FFT để chuyển đa thức sang miền tần số giúp nhân đa thức với độ phức tạp (O(n \log n))

Ý kiến của GN⁺

• Bài viết này giải thích cách nâng cao hiệu quả của phép nhân đa thức, đặc biệt nhấn mạnh tầm quan trọng của biến đổi Fourier nhanh (FFT)
• Nó cho thấy phương pháp này hiệu quả hơn rất nhiều so với cách cơ bản học ở trường phổ thông
• Kỹ thuật này có thể được ứng dụng hữu ích trong nhiều lĩnh vực như xử lý tín hiệu, xử lý ảnh, v.v.
• Việc dùng FFT cho phép thực hiện nhanh phép nhân của các đa thức lớn, nhờ đó có lợi cho xử lý dữ liệu quy mô lớn
• Các dự án khác có chức năng tương tự gồm NumPy, SciPy, v.v.