Convolução, Transformada Rápida de Fourier e Polinômios (2022)

Polinômios, Transformada Rápida de Fourier e Convolução

Polinômios: um resumo simples

• Um polinômio (P(x)) é a soma de termos em que cada termo é composto pela variável (x), o expoente (k) e o coeficiente (a_k)
• Exemplo: (P(x) = 5x^2 + 2x + 9)
• Somar ou subtrair dois polinômios (P(x)) e (Q(x)) significa somar ou subtrair cada termo individualmente
• Exemplo de código em Python:

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

Convolução

• Convolução é a composição de dois sinais (p) e (q)
• Exemplo: (p = [2, 3, 4]), (q = [5, 6, 7])
• Cálculo da convolução:

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

• A multiplicação de polinômios pode ser expressa como convolução

Transformada de Fourier e FFT

• A transformada de Fourier é uma ferramenta poderosa para converter sinais do domínio do tempo para o domínio da frequência
• Diferenças entre transformada de Fourier (FT), transformada discreta de Fourier (DFT) e transformada rápida de Fourier (FFT):
  • FT: transformada de Fourier para sinais contínuos
  • DFT: transformada de Fourier para sinais discretos
  • FFT: algoritmo que calcula a DFT de forma eficiente ((O(n \log n)))

Acelerando a multiplicação de polinômios

• A multiplicação de polinômios aprendida no ensino médio tem complexidade (O(n^2))
• Um método mais eficiente:
  1. Converter os polinômios para o domínio da frequência ((O(n \log n)))
  2. Multiplicar no domínio da frequência ((O(n)))
  3. Converter o resultado de volta para o domínio do tempo ((O(n \log n)))
• Exemplo de código em 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()
  

Resumo

• O método básico de multiplicação de polinômios tem complexidade (O(n^2))
• A multiplicação de polinômios pode ser expressa como convolução
• A convolução no domínio do tempo é equivalente à multiplicação no domínio da frequência
• Ao usar FFT para converter polinômios para o domínio da frequência, é possível multiplicá-los com complexidade (O(n \log n))

Opinião do GN⁺

• Este texto explica como aumentar a eficiência da multiplicação de polinômios e destaca especialmente a importância da transformada rápida de Fourier (FFT)
• Mostra que ela é muito mais eficiente do que o método básico aprendido no ensino médio
• Essa técnica pode ser usada de forma útil em várias áreas, como processamento de sinais e processamento de imagens
• Com FFT, é possível multiplicar rapidamente polinômios grandes, o que é vantajoso para processamento de dados em larga escala
• Outros projetos com funcionalidades semelhantes incluem NumPy e SciPy