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

 (alvarorevuelta.com)
1 pontos por GN⁺ 2024-07-02 | 1 comentários | Compartilhar no WhatsApp
  • Expandir polinômios de grau alto da forma ensinada no ensino médio exige multiplicar todos os pares de termos, então o custo O(n²) rapidamente se torna um gargalo
  • A multiplicação dos vetores de coeficientes de polinômios é equivalente à convolução de sinais discretos, e o resultado de [2, 3, 4] e [5, 6, 7] é [10, 27, 52, 45, 28]
  • A DFT leva um sinal discreto para o domínio da frequência, e a FFT calcula a mesma transformação em O(n log n), fazendo diferença em entradas grandes
  • Como a convolução no domínio do tempo se transforma em multiplicação elemento a elemento no domínio da frequência, é possível multiplicar polinômios mais rapidamente convertendo com FFT, multiplicando e depois retornando com IFFT
  • Em graus pequenos, o custo de ida e volta de FFT/IFFT pode anular o ganho, mas à medida que o grau cresce, o método com FFT se torna mais eficiente

Por que a multiplicação de polinômios fica lenta

  • Um polinômio P(x) é representado como a soma de termos formados pelos coeficientes a_k e potências da variável x
    • Exemplo: P(x)=5x²+2x+9 é um polinômio de grau 2
    • Dependendo da notação, o vetor de coeficientes pode ser escrito como [5, 2, 9] ou [9, 2, 5]
  • Soma e subtração são relativamente simples, pois basta somar ou subtrair os termos de mesmo grau
    • Em Python, é possível percorrer cada coeficiente com zip(p, q) e calcular a + b ou a - b
    • Se os graus forem diferentes, pode-se usar zip_longest
  • A multiplicação exige multiplicar cada termo pelos demais e depois somar novamente os termos de mesmo grau, o que aumenta o volume de cálculo
    • O resultado de (2x²+3x+4) × (5x²+6x+7) é 10x⁴+27x³+52x²+45x+28
    • A complexidade desse método é O(n²), e o número de multiplicações necessárias cresce com o grau

Vetores de coeficientes e convolução

  • No domínio discreto, a convolução de dois sinais p e q é definida como y[n]=Σ p[k]·q[n-k]
  • O cálculo é feito invertendo q e depois deslocando-o sobre p da esquerda para a direita, somando os produtos dos elementos sobrepostos
  • Os sinais de exemplo são os seguintes
    • p = [2, 3, 4]
    • q = [5, 6, 7]
  • Ao inverter e deslocar q, cada coeficiente de saída é gerado na seguinte ordem
    • 2×5 = 10
    • 2×6 + 3×5 = 27
    • 2×7 + 3×6 + 4×5 = 52
    • 3×7 + 4×6 = 45
    • 4×7 = 28
  • O resultado da convolução é y = [10, 27, 52, 45, 28]
    • Isso corresponde aos coeficientes de 10x⁴+27x³+52x²+45x+28, obtidos pela multiplicação dos polinômios
    • Portanto, a multiplicação de polinômios pode ser vista como a convolução dos vetores de coeficientes

Transformada de Fourier e FFT

  • A transformada de Fourier converte um sinal do domínio do tempo para o domínio da frequência
    • Na visão temporal, o sinal é observado como valores em instantes específicos
    • Na visão em frequência, o sinal é interpretado como a soma de diferentes frequências de oscilação
  • As frequências de oscilação são representadas por seno e cosseno, cada um com coeficiente e fase
  • Ao aplicar FFT a uma onda senoidal pura de 5Hz, ela aparece como um delta na posição de 5Hz no domínio da frequência
    • Isso mostra que a senoide no domínio do tempo pode ser expressa por um único seno de 5Hz
  • Os termos relacionados se distinguem assim
    • Fourier Transform (FT): transformada de Fourier definida no domínio contínuo
    • Discrete Fourier Transform (DFT): transformada de Fourier definida para sinais discretos
    • Fast Fourier Transform (FFT): algoritmo que calcula a DFT em O(n log n) em vez de O(n²)
  • A DFT transforma o sinal discreto no tempo x[n] em X[k] no domínio da frequência
    • Cada X[k] é calculado multiplicando as amostras de entrada por números complexos que representam uma frequência específica e somando os resultados

Transformando em multiplicação no domínio da frequência

  • A principal vantagem da DFT e do domínio da frequência é que a convolução pode ser convertida em multiplicação elemento a elemento
    • Convoluir dois sinais no domínio do tempo equivale a multiplicá-los no domínio da frequência
    • Multiplicação pode ser calculada mais rapidamente do que convolução
  • O procedimento para multiplicar polinômios com mais rapidez é o seguinte
    • Transformar os polinômios para o domínio da frequência com FFT: O(n log n)
    • Multiplicar elemento a elemento no domínio da frequência: O(n)
    • Transformar o resultado de volta para o domínio do tempo com IFFT: O(n log n)
  • No geral, usando FFT, a multiplicação de polinômios pode ser feita com complexidade O(n log n)
  • Para polinômios grandes, isso é mais rápido do que a multiplicação escolar em O(n²)

Implementação em Python e benchmark

  • multiply_naive multiplica todos os pares de coeficientes com um laço duplo e soma o resultado na posição i + j
    • O comprimento do resultado é len(p) + len(q) - 1
    • A complexidade é O(n²)
  • multiply_fft realiza a multiplicação dos coeficientes com base em FFT/IFFT
    • Ele calcula um comprimento que seja potência de 2 e pelo menos len(p) + len(q) - 1 para acomodar o tamanho do resultado
    • Usa np.pad para fazer padding nas duas entradas
    • Multiplica elemento a elemento os valores transformados com np.fft.fft
    • Depois volta com np.fft.ifft e arredonda a parte real para obter coeficientes inteiros
  • No exemplo com p = [2, 3, 4] e q = [5, 6, 7], os dois métodos retornam [10, 27, 52, 45, 28]
  • No benchmark, em vez de multiply_naive, compara-se o método com FFT com multiply_convolve, que usa np.convolve
    • Isso porque multiply_naive com laços em Python é lento demais para uma comparação direta com o método FFT usando np.fft.fft
    • np.convolve executa a mesma operação em código C de baixo nível
  • O grau é aumentado no intervalo range(1, 30000, 1000), e em cada grau são gerados dois polinômios com coeficientes aleatórios entre 1 e 999999
    • Em cada método, o tempo médio é medido com n_runs = 5
    • Em graus baixos, o custo da conversão de ida e volta com FFT/IFFT pode fazer o método FFT não ser vantajoso
    • À medida que o grau aumenta, o método com FFT mostra resultados muito mais eficientes

Leituras relacionadas

1 comentários

 
GN⁺ 2024-07-02
Comentários do Hacker News

  • O que sempre me incomoda em explicações assim é que normalmente se esquecem dos erros numéricos.
    Não dá para simplesmente abstrair a multiplicação dos coeficientes como “tempo constante”. Se for fazer isso, dá no mesmo abstrair a multiplicação inteira desde o começo. Levando em conta a precisão numérica, fica mais perto de O(n (log n)^3) [1]
    [1]: http://numbers.computation.free.fr/Constants/Algorithms/fft....

    • O limite de erro citado naquele texto é pessimista demais. A edição mais recente do Knuth traz o limite correto, porque eu avisei a ele
    • Seria bom se as operações baseadas em quatérnios mencionadas no post do OP pudessem ser usadas para reduzir, ou até eliminar, erros de multiplicação [1],[2],[3]
      [1] One-Dimensional Quaternion Discrete Fourier Transform and an Approach to Its Fast Computation:
      https://www.mdpi.com/2079-9292/12/24/4974
      [2] Convolution Theorems for Quaternion Fourier Transform: Properties and Applications:
      https://onlinelibrary.wiley.com/doi/10.1155/2013/162769
      [3] On the Matrix Form of the Quaternion Fourier Transform and Quaternion Convolution:
      https://arxiv.org/abs/2307.01836
    • Se os coeficientes forem inteiros, dá para obter um resultado exato com uma NTT usando um módulo suficientemente grande e, especialmente em hardware, o tempo de multiplicação também pode ficar mais rápido
    • É por isso que se acaba distinguindo ciência da computação de engenharia de software :)

  • Dá para multiplicar números longos usando esse método. O ponto principal é que a multiplicação de polinômios é igual à multiplicação longa comum de números grandes sem fazer o vai-um (carry).
    Por exemplo, se você tiver um número de 1000 dígitos, use cada dígito como coeficiente de um polinômio com 1000 elementos. Depois, dá para multiplicar esses polinômios com o método de FFT descrito no texto. Para transformar o resultado de volta em número, é preciso processar os carries. Se algum elemento for maior que 10, passa-se o excedente para a próxima casa e então se convertem os coeficientes em número.
    A ideia básica é essa, e há sutilezas na precisão necessária para os carries e em garantir que arredondar o resultado da FFT para o inteiro mais próximo ainda dê certo. É assim que a GMP, a principal biblioteca dessa área, faz multiplicação de números grandes

    • Como você disse, faz sentido, já que um número decimal pode ser representado como um polinômio com x=10. Por exemplo, 983 = 9x^2 + 8x + 3, ou seja, [9, 8, 3].
      Fico curioso sobre quão grande o número precisa ser para isso realmente fazer sentido, e onde isso é usado

  • Se ainda não viu, recomendo este vídeo
    https://youtu.be/h7apO7q16V0?si=bmgUEMTQSqU3flIv
    Ele deriva o algoritmo de FFT a partir da multiplicação de polinômios, e é realmente excelente. Reassisto mais ou menos a cada 6 meses

  • A propriedade da FFT de que “convolução é multiplicação ponto a ponto” também vale em qualquer grupo multiplicativo cíclico. Para uma derivação mais algébrica, veja https://www.sciencedirect.com/science/article/pii/S002200007...
    Às vezes chamam isso de “FFT harmônica”, e também existem FFTs não harmônicas: [LCH14] “additive NTT” sobre GF(2^n), [HLP24] circle FFT sobre o círculo unitário X^2+Y^2=1 em corpos finitos, e [BCKL21] ecfft sobre uma sequência de isogenias de curvas elípticas
    [LCH14]: https://arxiv.org/abs/1404.3458
    [HLP24]: https://eprint.iacr.org/2024/278
    [BCKL21]: https://arxiv.org/pdf/2107.08473

  • Quem foi a primeira pessoa a propor usar FFT para uma multiplicação de polinômios mais rápida?
    Fiquei curioso recentemente e fui procurar; embora eu não tenha conseguido rastrear muito bem as citações, cheguei até um artigo de 1995 de David Eppstein [0]. Nele, isso é usado para resolver de forma eficiente o problema da soma parcial após atualizações incrementais. Tenho quase certeza de que isso já aparecia antes no TAOCP, de Knuth
    Também foi bem chocante descobrir que é possível resolver o problema exato da soma de subconjuntos com repetição permitida em tempo subexponencial usando multiplicação de polinômios por FFT [1]. O ponto importante é que esse algoritmo é O(N log N), em que N não é o tamanho do conjunto, mas o maior elemento; portanto, não é algo como um contraexemplo a P ≠ NP
    [0] https://escholarship.org/content/qt6sd695gn/qt6sd695gn.pdf
    [1] https://x.com/festivitymn/status/1788362552998580473?s=46&t=...

  • Acho que todo aprendizado de máquina consiste em resolver equações de convolução
    Este artigo trata disso no contexto de aprendizado por reforço https://arxiv.org/abs/1712.06115, mas a maioria das abordagens se encaixa nesse paradigma

    • Basicamente, você quer dizer métodos de kernel, não?

  • Acabei de implementar um algoritmo (matrix profile) que usa FFT para calcular produtos internos de um grande conjunto de subsequências de séries temporais. O comprimento n da série temporal pode chegar à casa das centenas de milhões
    O cálculo rápido de convoluções usando FFT reduz o tempo de computação de O(n) para O(log n), e nessa escala o ganho de velocidade é enorme. Usando GPU, fica ainda mais rápido: algo como processar 10 milhões de pontos de dados em 0,1 segundo em um notebook

  • O “truque” central dessa operação parece ser esta percepção:

    Em outras palavras, realizar a convolução de dois sinais no domínio do tempo é o mesmo que multiplicar os dois sinais no domínio da frequência.
    É um ótimo texto, que divide uma ideia complexa em etapas muito menores, de modo que até eu, que sou fraco em matemática, consigo de algum jeito entender. Mas será que ele pulou uma etapa intermediária? Ou deixou como exercício para o leitor procurar? Até aquele ponto eu já estava usando toda a minha capacidade matemática, então pareceu um pouco aquele “e agora desenhe o resto da maldita coruja”. Só eu senti isso? O texto em si foi realmente muito bom

    • Não sei se ajuda, mas: a multiplicação de dois polinômios que se aprende na escola é, na prática, uma convolução
      Existe a propriedade de que “realizar a convolução de dois sinais no domínio do tempo é o mesmo que multiplicar os dois sinais no domínio da frequência”, e a FFT permite converter do domínio do tempo para o domínio da frequência. Então levamos os polinômios para o domínio da frequência com FFT e, nesse domínio, basta multiplicar. É mais rápido do que a convolução. Fico curioso se isso deixa clara a etapa que estava faltando; se ainda houver alguma lacuna, posso atualizar o texto

  • Então a fatoração de inteiros seria uma deconvolução discreta? Fico me perguntando se, ao colocar lado a lado a representação por FFT, isto é, a operação inversa da multiplicação ponto a ponto, e tableax, isto é, a multiplicação longa/soma com transporte comum, a simetria se quebra e fornece informações suficientes para um algoritmo rápido

  • Claro, a multiplicação ingênua de polinômios é lenta em relação ao grau do polinômio. Mas, na prática, quando é que alguém precisa lidar com dois polinômios de grau 100?
    Por esse motivo, fica a impressão de que sistemas de álgebra computacional não usam esse método

    • Sistemas de álgebra computacional, por exemplo o chebfun do Matlab, transformam funções arbitrárias em polinômios de grau 100 ou mais para encontrar raízes, valores ótimos etc. com mais facilidade
    • É muito comum em correção de erros e processamento de sinais
      https://www.youtube.com/watch?v=CcZf_7Fb4Us
      https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor... é um exemplo
    • Como eu queria fazer engenharia reversa dos parâmetros de checksum CRC de arquivos grandes, criei um programa[1] que converte o arquivo em um polinômio GF(2) de milhões de graus e calcula o máximo divisor comum. Sem multiplicação baseada em FFT, isso não seria possível em um tempo razoável
      [1]: https://github.com/8051enthusiast/delsum
    • Essa perspectiva de convolução e kernels rápidos de GPU para FFT foram usados em alguns modelos de espaço de estados anteriores ao Mamba para modelagem de sequências longas; nesse caso, o polinômio é a sequência de entrada
      Os posts do blog da Hazy Research de 2020 a 2023 têm bastante informação sobre essa abordagem
    • Consulte https://news.ycombinator.com/item?id=40306339
      “(...) Em uma pesquisa de física, já lidei com uma expressão de quase 1 terabyte de comprimento e com mais de 100 milhões de termos”