Complexidade da computação da transformada discreta de Fourier?

18

Qual é a complexidade (na RAM inteira padrão) de calcular a transformada discreta padrão de Fourier de um vetor de números inteiros?n

O algoritmo clássico para transformações rápidas de Fourier , atribuídas inadequadamente [1] a Cooley e Tukey, é geralmente descrito como sendo executado em tempo . Mas a maioria das operações aritméticas executadas neste algoritmo começar com complexos n º raízes da unidade, que são (para a maioria n ) irracional, avaliação de modo exato no tempo constante não é razoável. O mesmo problema ocorre com o algoritmo ingênuo de tempo O ( n 2 ) (multiplicado por uma matriz de Vandermonde de raízes complexas da unidade).O(nlogn)nnO(n2)

Nem está claro como representar exatamente a saída do DFT (de qualquer forma útil). Em outras palavras, não está claro que a computação DFTs seja realmente possível!

Então, suponha que precisamos apenas de bits de precisão em cada valor de saída. Qual é a complexidade de calcular a discreta transformada de Fourier, em função de n e b ? (Para concretude, sinta-se à vontade para assumir que n é uma potência de 2 ).bnbn2

Ou todos os exemplos de "FFT" na literatura realmente significam "rápida transformação teórica dos números "? [2]

Veja minhas perguntas relacionadas sobre a complexidade da eliminação gaussiana e os caminhos mais curtos euclidianos .

[1] Deveria realmente ser chamado (algum prefixo) do algoritmo Gauss-Runge-König-Yates-Stumpf-Danielson-Lánczos-Cooley-Tukey.

[2] E se sim, por que a maioria dos livros descreve apenas o algoritmo de números complexos?

Jeffε
fonte
1
Eu acho que esse é o ponto dele: em teoria, você não precisa se preocupar com , mas em qualquer implementação REAL, você precisa se preocupar com isso e com o erro que possa ocorrer. b
Suresh Venkat
1
Na verdade, essa é uma boa pergunta: cada bit adicional de precisão adiciona à força do sinal (multiplique por 2 ). Então, acho que a pergunta será mais útil se os tamanhos intermediários de palavras puderem ser expandidos! 3dB2
vs
3
A análise computável considerou isso e questões relacionadas. Este artigo produz uma complexidade vinculada ao cálculo da transformada de Fourier dentro da estrutura da efetividade do tipo II de Weirauch. O limite é que ele é linear na apresentação da entrada (infinita, com valor real). Tanto a entrada quanto a saída são definidas por parâmetros de precisão neste sistema, portanto, pode haver uma maneira de traduzir isso no modelo de RAM.
Aaron Sterling
3
Veja o método A no artigo de Schönhage e Strassen sobre multiplicação inteira. Ele usa transformadas complexas de Fourier com precisão limitada. Eu acho que também é descrito em Knuth, vol. 2.
Markus Bläser
2
Markus, Aaron: converter em respostas?
Suresh Venkat

Respostas:

9

Esta resposta é uma variante da análise do primeiro algoritmo ("Método A") de Schönhage e Strassen para multiplicação de números inteiros longos.

Suponha que queremos calcular uma FFT de comprimento . Escale a sua entrada de forma que todos os valores são menores do que 1. Vamos primeiro assumir que calculamos com m bits fixa aritmética de ponto ( m pedaços após o ponto binário). Deixe δ = 2 1 / 2 - m ser o ( "complexo") unidade de menos posição. Seja ω = exp ( 2 π i / K ) .K=2kmmδ=21/2mω=exp(2πi/K)

1) Pode-se calcular aproximações tais que | ω j - ω j | ( 2 k - 1 ) δ para todos os 0 j K - 1 . Isso pode ser feito no tempo O ( K M ( mωj|ωjωj|(2k1)δ0jK1 onde M ( m ) é o tempo necessário para multiplicar osnúmeros de bits m . (veja Knuth Vol. 2, 3ª ed., página 309).O(KM(m))M(m)m

Se a RAM inteira padrão significa custo logarítmico, então . Se RAM inteira padrão significa palavra RAM, então M ( m ) = O ( m ) . (Schönhage e Strassen mostram no "Método A" como reduzir em tempo linear a multiplicação de mM(m)=O(mlogm)M(m)=O(m)m números de bits para multiplicação de S ( log m ) mordeu números. O último pode ser feito em custos unitários.)mO(logm)

2) O clássico Cooley-Tukey FFT calcula operações da forma . Utilizamos aritmética de ponto fixo m- bit, essas operações se tornam a ' = t r u n c a t e ( b + ω ' j c ' ) . Se sabemos b ' e c 'a=b+ωjcma=truncate(b+ωjc)bc até um erro de , temos um ' até um erro de 2 ε + 2ϵa .2ϵ+2kδ

3) Usando indução, é fácil ver que obtemos o resultado final com erro . Para obter precisão b no final, m k + log k + b + O ( 1 ) . (2k1)2kδbmk+logk+b+O(1)

4) Assim, o tempo final de execução é .O(KkM(k+b))

Isso também deve funcionar com números de ponto flutuante: 1) ainda pode ser feito com aritmética de ponto fixo, 2) também é verdadeiro para números de ponto flutuante.


Na aritmética de ponto fixo, eu acho, isso pode ser feito mais rapidamente. Primeiro, reduzimos o cálculo da FFT à multiplicação de polinômios usando o truque de Bluestein. O comprimento dos coeficientes necessários para obter a precisão desejada deve ser . Em seguida, reduzimos a multiplicação de polinômios à multiplicação de números inteiros longos. (Anexe os coeficientes a um número longo e separe-os por blocos com zero de comprimento O ( k + b ) .) O comprimento dos números inteiros é O (O(k+b)O(k+b) .O(K(k+b))

Markus Bläser
fonte
O(nlog2n)
O(nlogn)O(k+b)
2
bO(logn)O(nlogn)M(O(logn))=1
Por acaso, observei o livro de Aho, Hopcroft e Ullman em "O Projeto e Análise de Algoritmos" e eles discutiram o algoritmo no modelo de bits e questões relacionadas com mais detalhes.
Chandra Chekuri 21/09/11
Mas, tanto quanto me lembro, eles discutem apenas a "FFT teórica dos números" no modelo de bits.
Markus Bläser
8

Esta não é uma resposta completa, mas posso apontar alguns artigos relevantes e também parcialmente explicar por que não é tão fácil extrair uma resposta para sua pergunta específica da literatura.

Deixe-me começar perguntando: por que você quer saber a resposta para esta pergunta? Normalmente, as pessoas que se preocupam com esse tipo de problema são aquelas que realmente implementam uma FFT de alto desempenho para uma aplicação prática. Essas pessoas se preocupam menos com a complexidade assintótica em algum modelo computacional idealizado do que com a maximização do desempenho sob suas restrições particulares de hardware e software. Por exemplo, os desenvolvedores da transformação mais rápida de Fourier no Ocidente escrevem em seu artigo:

A melhor escolha depende dos detalhes do hardware, como número de registros, latência e taxa de transferência de instruções, tamanho e associatividade dos caches, estrutura do pipeline do processador, etc.

São questões com as quais os teóricos normalmente não querem manchar suas mãos, mas são de grande importância nas implementações reais. Se um teórico declara: "Eu descobri a melhor complexidade absoluta de bits assintóticos no modelo de RAM", o praticante pode dizer: "Isso é legal", mas pode achar esse resultado teórico inútil para seus propósitos.

Dito isto, acho que sua melhor aposta é examinar a literatura de análise numérica. Por exemplo, Tasche e Zeuner examinaram atentamente a estabilidade numérica do algoritmo FFT. Talvez isso ainda não seja exatamente o que você deseja, porque o consenso geral entre os profissionais parece ser que, para alcançar uma certa quantidade de precisão numérica, a melhor abordagem prática é pré - calcular certos números chamados "fatores de twiddle" com alta precisão. Se você estiver executando apenas uma FFT, essa não será a abordagem mais rápida, porque você não poderá amortizar o custo de sua pré-computação única em um grande número de cálculos de FFT. Ainda assim, a análise deles do pior erro de arredondamento ainda deve ser relevante para sua pergunta.

Timothy Chow
fonte
11024100
1
Estou interessado como uma questão puramente teórica, no interesse de uma bolsa de estudos correta e honesta. É bastante comum ler "e aqui usamos uma FFT, que como todos sabem, é executada no tempo O (n log n)" no meio de um algoritmo de outra maneira puramente combinatória, analisado em termos de passagens de ponteiro e O (log n ) aritmético inteiro de bits. Se, de fato, a convolução inteira pode ser realizada no tempo O (n log n) usando uma ligeira variante da FFT, isso talvez seja perdoável, mas ainda assim desleixado. Caso contrário, qualquer pobre idiota que tentar implementar o algoritmo receberá A RESPOSTA ERRADA.
Jeffε
E, é claro, não espero que a resposta à minha pergunta tenha qualquer impacto na prática.
Jeffε
2
Jeff, no que diz respeito a uma bolsa de estudos honesta, não basta dizer que a FFT exige operações de anel O (n log n)? Essa é a maneira natural de medir a complexidade do algoritmo FFT. Não vejo a motivação para converter tudo em um modelo específico de computação. Há algum teorema que você está tentando provar, onde é crucial acompanhar o número de bits de precisão? Quanto ao seu pobre idiota, não acredito que ele receba a "resposta errada". Em qualquer implementação real, é muito improvável que a pergunta que você está fazendo aqui seja a preocupação dominante.
Timothy Chow
O(nlogn)