|
== Introdução ==
A '''Transformada rápida de Fourier''' (em inglês fast Fourier transform, ou '''FFT''') é um algoritmo eficiente para se calcular a [[Transformada de Fourier|Transformada discreta de Fourier]] ('''DFT''') e a sua inversa. A análise de Fourier converte um sinal do seu domínio original para uma representação no domínio da frequência e vice-versa. Uma Transformada rápida de Fourier calcula rapidamente essas transformações fatorizando a matriz da Transformada discreta de Fourier em um produto de fatores esparsos (principalmente zero).<ref>{{Citar livro|url=http://dx.doi.org/10.1137/1.9781611970999|título=Computational Frameworks for the Fast Fourier Transform|ultimo=Van Loan|primeiro=Charles|data=1992-01|editora=Society for Industrial and Applied Mathematics|isbn=9780898712858}}</ref>. Como resultado, ele consegue reduzir a complexidade de calcular a Transformada discreta de Fourier de '''''O(n<sup>2</sup>)''''', ou seja na ordem de n elevado ao quadrado, que surge se alguém simplesmente aplica a definição de Transformada discreta de Fourier, a '''''O( n log n)''''', onde '''''n''''' é o tamanho dos dados.
As Transformadas rápidas de Fourier são de grande importância em uma vasta gama de aplicações, de [[Processamento digital de sinais]] para a resolução de [[Equação diferencial parcial|equações diferenciais parciais]] a algoritmos para multiplicação de grandes inteiros. Transformadas rápidas de Fourier são amplamente utilizadas para aplicações diversas em engenharia, ciência e matemática. As idéias básicas foram popularizadas em 1965, mas alguns algoritmos foram obtidos em 1805.<ref>{{Citar periódico|ultimo=Heideman|primeiro=Michael T.|ultimo2=Johnson|primeiro2=Don H.|ultimo3=Burrus|primeiro3=C. Sidney|data=1985|titulo=Gauss and the history of the fast Fourier transform|url=http://dx.doi.org/10.1007/bf00348431|jornal=Archive for History of Exact Sciences|volume=34|numero=3|paginas=265–277|doi=10.1007/bf00348431|issn=0003-9519}}</ref> Em 1994, Gilbert Strang descreveu a Transformada rápida de Fourier como "O algoritmo numérico mais importante da nossa vida.",<ref>{{Citar livro|url=https://www.worldcat.org/oclc/48024997|título=The acoustic analysis of speech|ultimo=D.|primeiro=Kent, Raymond|data=2002|editora=Singular/Thomson Learning|edicao=2nd |local=Australia|isbn=0769301126|oclc=48024997}}</ref><ref>{{Citar periódico|ultimo=Strang|primeiro=Gilbert|data=1984-04|titulo=Duality in the Classroom|url=http://dx.doi.org/10.2307/2322961|jornal=The American Mathematical Monthly|volume=91|numero=4|paginas=250|doi=10.2307/2322961|issn=0002-9890}}</ref> e foi incluída no Top 10 Algorithms of 20th Century pela revista IEEE Computing in Science & Engineering.<ref>{{Citar periódico|data=2018-07-12|titulo=Institute of Electrical and Electronics Engineers|url=https://en.wikipedia.org/w/index.php?title=Institute_of_Electrical_and_Electronics_Engineers&oldid=850008218|jornal=Wikipedia|lingua=en}}</ref>Computing in Science & Engineering.
== História ==
O desenvolvimento de algoritmos rápidos para Transformada discreta de Fourier pode ser rastreado até o trabalho não publicado de [[Carl Friedrich Gauss|Gauss]] em 1805, quando ele precisou interpolar a órbita dos asteróides [[Asteroide Pallas|Pallas]] e [[Asteroide Juno|Juno]] de observações de amostras.<ref>{{Citar periódico|ultimo=Heideman|primeiro=Michael T.|ultimo2=Johnson|primeiro2=Don H.|ultimo3=Burrus|primeiro3=C. Sidney|data=1985|titulo=Gauss and the history of the fast Fourier transform|url=http://dx.doi.org/10.1007/bf00348431|jornal=Archive for History of Exact Sciences|volume=34|numero=3|paginas=265–277|doi=10.1007/bf00348431|issn=0003-9519}}</ref>.<ref>{{Citar periódico|ultimo=Gauss|primeiro=Carl Friedrich|data=1877|titulo=Auszug aus dreijährigen täglichen Beobachtungen der magnetischen Declination zu Göttingen|url=http://dx.doi.org/10.1007/978-3-642-49319-5_34|local=Berlin, Heidelberg|publicado=Springer Berlin Heidelberg|paginas=556–568|isbn=9783642493201}}</ref> Seu método foi muito semelhante ao publicado em 1965 por [[James William Cooley]] e [[John Wilder Tukey]], que são geralmente creditados pela invenção do moderno algoritmo de Transformada rápida de Fourier genérico. Enquanto o trabalho de [[Carl Friedrich Gauss|Gauss]] antecedeu os resultados de [[Jean Baptiste Joseph Fourier|Fourier]] em 1822, ele não analisou o tempo de computação e, eventualmente, usou outros métodos para atingir seu objetivo.
Entre 1805 e 1965, algumas versões da Transformada rápida de Fourier foram publicadas por outros autores. [[Frank Yates]], em 1932, publicou sua versão chamada algoritmo de interação, que forneceu uma computação eficiente das [[:en:Hadamard_transform|transformadas de Hadamard e Walsh]].<ref>{{Citar periódico|ultimo=Heideman|primeiro=Michael T.|ultimo2=Johnson|primeiro2=Don H.|ultimo3=Burrus|primeiro3=C. Sidney|data=1985|titulo=Gauss and the history of the fast Fourier transform|url=http://dx.doi.org/10.1007/bf00348431|jornal=Archive for History of Exact Sciences|volume=34|numero=3|paginas=265–277|doi=10.1007/bf00348431|issn=0003-9519}}</ref>. O algoritmo de Yates ainda é usado no campo do projeto estatístico e análise de experimentos. Em 1942, [[:en:G._C._Danielson|G. C. Danielson]] e [[Cornelius Lanczos]] publicaram sua versão para computar a Transformada discreta de Fourier para cristalografia de raios X, um campo onde o cálculo das transformadas de Fourier apresentava um formidável obstáculo.<ref>{{Citar periódico|ultimo=Michaelson|primeiro=S.|ultimo2=Lanczos|primeiro2=Cornelius|data=1960-02|titulo=Applied Analysis|url=http://dx.doi.org/10.2307/3608551|jornal=The Mathematical Gazette|volume=44|numero=347|paginas=75|doi=10.2307/3608551|issn=0025-5572}}</ref>.<ref>{{Citar periódico|ultimo=Danielson|primeiro=G.C.|ultimo2=Lanczos|primeiro2=C.|data=1942-04|titulo=Some improvements in practical Fourier analysis and their application to x-ray scattering from liquids|url=http://dx.doi.org/10.1016/s0016-0032(42)90767-1|jornal=Journal of the Franklin Institute|volume=233|numero=4|paginas=365–380|doi=10.1016/s0016-0032(42)90767-1|issn=0016-0032}}</ref> Embora muitos métodos no passado tenham se concentrado em reduzir o fator constante para computação de '''''O(n<sup>2</sup>)''''' aproveitando as "simetrias", Danielson e Lanczos perceberam que useusando a "periodicidade" e apliqueaplicando um "truque de duplicação" parapoderiam obter o tempo de execução '''''O( n log n)'''''.<ref>{{Citar periódico|ultimo=Cooley|primeiro=J.|ultimo2=Lewis|primeiro2=P.|ultimo3=Welch|primeiro3=P.|data=1967-06|titulo=Historical notes on the fast Fourier transform|url=http://dx.doi.org/10.1109/tau.1967.1161903|jornal=IEEE Transactions on Audio and Electroacoustics|volume=15|numero=2|paginas=76–79|doi=10.1109/tau.1967.1161903|issn=0018-9278}}</ref>
James Cooley e John Tukey publicaram uma versão mais geral da Transformada rápida de Fourier em 1965 que é aplicável quando N é composto e não necessariamente uma potência de 2.<ref>{{Citar periódico|ultimo=Cooley|primeiro=James W.|ultimo2=Tukey|primeiro2=John W.|data=1965-04|titulo=An Algorithm for the Machine Calculation of Complex Fourier Series|url=http://dx.doi.org/10.2307/2003354|jornal=Mathematics of Computation|volume=19|numero=90|paginas=297|doi=10.2307/2003354|issn=0025-5718}}</ref>. Tukey teve a idéia durante uma reunião do Comitê Consultivo Científico do presidente Kennedy, onde um tópico de discussão envolveu a detecção de testes nucleares pela União Soviética, através da instalação de sensores para cercar o país de fora. Para analisar a saída desses sensores, seria necessário um algoritmo de transformação rápida de Fourier. Em discussão com Tukey, Richard Garwin reconheceu a aplicabilidade geral do algoritmo não apenas a problemas de segurança nacional, mas também a uma ampla gama de problemas, incluindo um de interesse imediato para ele, determinandodeterminar as periodicidades das orientações de ''spin'' em um cristal 3-D. de hélio-3.<ref>{{Citar periódico|ultimo=Cooley|primeiro=James W.|data=1987-01|titulo=The re-discovery of the fast Fourier transform algorithm|url=http://dx.doi.org/10.1007/bf01201681|jornal=Mikrochimica Acta|volume=93|numero=1-6|paginas=33–45|doi=10.1007/bf01201681|issn=0026-3672}}</ref> Garwin deu a idéia de Tukey para Cooley (ambos trabalharam nos laboratórios Watson da IBM) para implementação.<ref>{{Citar periódico|ultimo=Cooley|primeiro=J.|ultimo2=Garwin|primeiro2=R.|ultimo3=Rader|primeiro3=C.|ultimo4=Bogert|primeiro4=B.|ultimo5=Stockham|primeiro5=T.|data=1969-06|titulo=The 1968 Arden house workshop on fast Fourier transform processing|url=http://dx.doi.org/10.1109/tau.1969.1162047|jornal=IEEE Transactions on Audio and Electroacoustics|volume=17|numero=2|paginas=66–76|doi=10.1109/tau.1969.1162047|issn=0018-9278}}</ref>. Cooley e Tukey publicaram o artigo em um período relativamente curto de seis meses. <ref>{{Citar periódico|ultimo=Rockmore|primeiro=D.N.|data=2000|titulo=The FFT: an algorithm the whole family can use|url=http://dx.doi.org/10.1109/5992.814659|jornal=Computing in Science & Engineering|volume=2|numero=1|paginas=60–64|doi=10.1109/5992.814659|issn=1521-9615}}</ref> Como Tukey não trabalhava na IBM, a patenteabilidade da ideia foi posta em dúvida e o algoritmo entrou no domínio público, o que, através da revolução da computação na próxima década, fez da FFT um dos algoritmos indispensáveis no processamento digital de sinais.
== Visão Geral ==
|
