Esercizio - domande di prima parte su polinomi, DFT e FFT (simulazioni d'esame)

---

Teoria usata: DFT, matrice di Fourier e radici n-esime dell'unitàla DFT di ordine n valuta un polinomio di grado limitato da n sulle n radici n-esime dell'unità, y_i = p(ω^i) con ω = e^{2πi/n}; è il prodotto per la matrice di Fourier F_n, una Vandermonde invertibile. Le radici formano un gruppo moltiplicativo e valgono tre lemmi: cancellazione (ω_{dn}^{dk} = ω_n^k, ω_n^{n/2} = -1), dimezzamento (i quadrati delle n radici sono le n/2 radici n/2-esime, ciascuna due volte) e somma (la somma delle potenze di ω^k vale n se k è multiplo di n, 0 altrimenti). Teorema di convoluzione lineare: (c|0) = DFT^{-1}{2n}(DFT{2n}(a|0) ⊙ DFT_{2n}(b|0)).DFT, matrice di Fourier e radici n-esime dell'unità →, Trasformate notevoli ed esponenziazione di polinomi con la FFTalcune famiglie di vettori hanno DFT nota o più economica della FFT generale: il vettore costante (a,...,a) ha DFT (na,0,...,0), il vettore (a,0,...,0) ha DFT (a,...,a); un vettore (n,k)-sparso ha DFT formata da k copie della DFT_{n/k} delle sue componenti di indice multiplo di k, e SPARSE_FFT costa 2 (n/k) log2(n/k) con ricorrenza T(n,k) = T(n/2,k/2). Per la potenza p(x)^k di un polinomio con n coefficienti: o si eleva a potenza per quadrature successive con LIN_CONV, O(nk log(nk)), oppure si valuta p con la FFT su h = 2^ceil(log2((n-1)k+1)) punti, si eleva alla k ogni valore e si antitrasforma, Theta(nk log(nk)).Trasformate notevoli ed esponenziazione di polinomi con la FFT →, Fast Fourier Transform - algoritmo ricorsivo e trasformata inversala FFT calcola DFT_n (n potenza di due) con divide et impera: si separano i coefficienti di indice pari e dispari, p(x) = p0(x^2) + x p1(x^2), e per il lemma di dimezzamento bastano due DFT di ordine n/2; y_i = y0_i + w^i y1_i e y_{i+n/2} = y0_i - w^i y1_i. La ricorrenza T(n) = 2T(n/2) + 2n con T(1) = 0 ha soluzione esatta 2 n log2 n. L'inversa ha matrice F^{-1}_{ij} = w^{-ij}/n: si ottiene con la FFT sulle potenze negative (poi si divide per n fuori dalla ricorsione) oppure con DFT_n(y) rovesciato. LIN_CONV moltiplica due polinomi con n coefficienti in 12 n log2(2n) + 4n operazioni.Fast Fourier Transform - algoritmo ricorsivo e trasformata inversa →.

Domanda 1: parte reale e parte immaginaria di $\omega_{16}^{120}$

Si determini la parte reale ($\mathrm{Re}$) e la parte immaginaria ($\mathrm{Im}$) di $\omega_{16}^{120}$. Scegli un'alternativa:

• $\mathrm{Re}(\omega_{16}^{120})=1$ e $\mathrm{Im}(\omega_{16}^{120})=0$
• $\mathrm{Re}(\omega_{16}^{120})=0$ e $\mathrm{Im}(\omega_{16}^{120})=1$
• $\mathrm{Re}(\omega_{16}^{120})=0$ e $\mathrm{Im}(\omega_{16}^{120})=-1$
• $\mathrm{Re}(\omega_{16}^{120})=-1$ e $\mathrm{Im}(\omega_{16}^{120})=0$

Risposta: la quarta, $\omega_{16}^{120}=-1$.

Metodo 1, periodicità. Le potenze di $\omega_n$ hanno periodo $n$ nell'esponente: $\omega_n^k=\omega_n^{k\bmod n}$. Con $120=7\cdot16+8$ si ha $120\bmod16=8$, quindi $\omega_{16}^{120}=\omega_{16}^{8}$. Per il lemma di cancellazione $\omega_{16}^{8}=\omega_{2\cdot8}^{1\cdot8}=\omega_2^1=e^{i\pi}=-1$ (mezzo giro). In generale $\omega_n^{n/2}=-1$.

Metodo 2, cancellazione ripetuta (più veloce se ordine ed esponente sono pari): $$\omega_{16}^{120}=\omega_8^{60}=\omega_4^{30}=\omega_2^{15}=\omega_2^{1}=-1,$$ dove ogni passaggio divide ordine ed esponente per $2$ e l'ultimo usa $\omega_2^{15}=(-1)^{15}=-1$.

Metodo 3, angolo. $\omega_{16}^{120}=e^{2\pi i\cdot120/16}=e^{i\,15\pi}$: sono $7$ giri completi più mezzo giro, cioè il punto $-1$ (controllato numericamente: il risultato è $-1$ con una parte immaginaria dell'ordine di $10^{-15}$, errore di arrotondamento).

Le altre risposte corrispondono a $1$ (esponente multiplo di $16$), $i$ (esponente $\equiv4$) e $-i$ (esponente $\equiv12$ modulo $16$).

Domanda 2: DFT di un vettore quasi costante

Sia $\mathbf x=(5,3,3,3,4,3,3,3)$. Calcolare $\mathbf y=\mathrm{DFT}_8(\mathbf x)$. Scegli un'alternativa:

• $(27,1,3,1,3,1,3,1)$
• $(27,3,1,3,1,3,1,3)$
• $(26,0,10,0,10,0,10,0)$
• $(26,0,6,0,6,0,6,0)$

Risposta: la prima, $\mathbf y=(27,1,3,1,3,1,3,1)$.

Metodo veloce, linearità e trasformate notevoli. La DFT è lineare ($\mathrm{DFT}_n(\mathbf u+\mathbf v)=\mathrm{DFT}_n(\mathbf u)+\mathrm{DFT}_n(\mathbf v)$, perché $F_n$ è una matrice). Il vettore si scompone in $$\mathbf x=\underbrace{(3,3,3,3,3,3,3,3)}_{\text{costante}}+\underbrace{(2,0,0,0,1,0,0,0)}_{(8,4)\text{-sparso}}.$$

• Il vettore costante ha $\mathrm{DFT}_8(3,\dots,3)=(8\cdot3,0,\dots,0)=(24,0,0,0,0,0,0,0)$ (lemma di somma).
• Il vettore $(8,4)$-sparso (componenti non nulle solo agli indici multipli di $4$) ha DFT formata da $k=4$ copie della $\mathrm{DFT}_{8/4}=\mathrm{DFT}_2$ del vettore delle componenti di indice multiplo di $4$, cioè $(2,1)$: $\mathrm{DFT}_2(2,1)=\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}2\\1\end{pmatrix}=(3,1)$, ripetuta $4$ volte: $(3,1,3,1,3,1,3,1)$.

Sommando: $\mathbf y=(24+3,\,0+1,\,0+3,\,0+1,\,0+3,\,0+1,\,0+3,\,0+1)=(27,1,3,1,3,1,3,1)$.

Metodo per eliminazione, senza calcolare tutta la DFT. Bastano due componenti:

• $y_0=\sum_jx_j=5+3+3+3+4+3+3+3=27$ (la riga $0$ di $F_8$ è di soli $1$): esclude le risposte $3$ e $4$, che hanno $y_0=26$;
• $y_4=\sum_jx_j(-1)^j=5-3+3-3+4-3+3-3=3$ (perché $\omega_8^{4j}=(-1)^j$): la seconda risposta ha $y_4=1$, quindi è esclusa; la prima ha $y_4=3$.

Controllo. Calcolando $\mathrm{DFT}_8(\mathbf x)$ dalla definizione (somma $\sum_jx_j\omega_8^{ij}$ per $i=0,\dots,7$) con un programma si ottiene $(27,1,3,1,3,1,3,1)$ a meno di errori di arrotondamento dell'ordine di $10^{-15}$.