Analisi degli Algoritmi di FFT ed Applicazioni alla Moltiplicazione Rapida di Polinomi

La Trasformata di Fourier, una delle scoperte scientifiche più rivoluzionarie del 19-esimo secolo, è l’operatore matematico fondamentale per poter analizzare segnali nel tempo. Se nella teoria quest’ultimi sono rappresentati da funzioni continue e periodiche, nella pratica l’analisi si basa su singoli campioni discreti: lo strumento matematico adeguato a tale studio è la Trasformata Discreta di Fourier (DFT). Se da un lato tale trasformazione risolve il problema di implementare la Trasformata di Fourier al calcolatore, dall’altro presenta un grande difetto: l’enorme complessità computazionale. L’obiettivo del seguente elaborato è di analizzare vari algoritmi ottimizzati che risolvono questa criticità, ovvero gli algoritmi di FFT, con implementazioni in Matlab, contestualizzando le varie scoperte nel periodo storico di riferimento. Inoltre, anche se questi metodi sono principalmente utilizzati in ambiti pratici, come, ad esempio, nell’elaborazione di audio ed immagini, nelle telecomunicazioni, nello spettroscopia, si conclude descrivendo una loro originale applicazione algebrica alla moltiplicazione rapida di polinomi, e il conseguente impatto che tale procedimento ha avuto nell’ottimizzazione del calcolo di prodotti di numeri interi.