A teoria da complexidade aritmética

Neste trabalho é introduzida a teoria para se obter algoritmos otimizados para qualquer transformada linear. Uma aplicação direta dessa teoria resulta na construção da transformada rápida de Fourier otimizada, a qual atinge o número mínimo possível de multiplicações, sendo mais eficiente do que qualquer algoritmo conhecido na literatura, para computar a transformada discreta de Fourier. O texto também mostra técnicas para diminuir o número de adições em transformadas e implementações utilizando linguagem de descrição de hardware.