Esercizio - polinomio con tutte le radici dell'unità tranne 1 e -1, valutazione e DFT dei coefficienti (compito del 26 giugno 2025, es. 1)

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à → (DFT come valutazione sulle radici, lemma di somma), 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 → (matrice inversa di Fourier), 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 → (vettori $(n,k)$-sparsi), Polinomi - rappresentazione per coefficienti e per valori e convoluzioneun polinomio di grado limitato da n si rappresenta con n coefficienti o con n valori su n punti distinti (teorema di interpolazione, matrice di Vandermonde). Per coefficienti la somma costa n e il prodotto, la convoluzione lineare, n^2 prodotti e (n-1)^2 somme; per valori il prodotto costa 2n-1 prodotti ma serve una base estesa di almeno 2n-1 punti. Le conversioni generali costano troppo: valutazione n volte con Horner 2n(n-1), interpolazione con Gauss-Jordan n^3 o con Lagrange n^2. Serve una base speciale: la DFT.Polinomi - rappresentazione per coefficienti e per valori e convoluzione → (valutazione).

Il polinomio è dato in forma fattorizzata: non si conoscono i coefficienti $a_i$, ma si sa valutarlo in un punto $z$ con un prodotto di $n-2$ fattori. Questo è il dato di partenza di tutto l'esercizio.

(a) Un algoritmo semplice per $p_n(1)$ e $p_n(-1)$

Si calcolano le potenze $\omega_n^h$ una dopo l'altra e si accumulano i due prodotti $\prod_h(1-\omega_n^h)$ e $\prod_h(-1-\omega_n^h)$, saltando $h=n/2$ (il fattore mancante) e partendo dal primo fattore senza moltiplicare per $1$.

A0(n)
w <- e^(i 2 pi / n)                       { costante: non si conta }
pw <- w                                   { pw = w^h all'inizio dell'iterazione h }
for h <- 1 to n-1
    if h >= 2 then pw <- pw * w           { n-2 prodotti }
    if h != n/2 then
        f1 <- 1 - pw;   f2 <- -(1 + pw)   { 2 operazioni }
        if è il primo fattore then P1 <- f1; P2 <- f2
        else P1 <- P1 * f1;  P2 <- P2 * f2   { 2 prodotti }
return (P1, P2)

I fattori utili sono $h=1,\dots,n-1$ con $h\ne n/2$, cioè $n-2$ fattori. Conteggio:

• aggiornamenti di pw: $n-2$ prodotti;
• calcolo dei fattori: $2(n-2)$ operazioni;
• accumulo: i due prodotti partono dal secondo fattore, quindi $2(n-3)$ prodotti.

Totale: $T_a(n)=(n-2)+2(n-2)+2(n-3)=5n-12$ operazioni (verificato contando le operazioni di un'implementazione per $n=4,8,16,32$: $8,28,68,148$). La soluzione del corso riporta $5n-13$: calcola $3n-8$ per ciascuna valutazione contando $n-3$ potenze, e condivide le potenze tra le due valutazioni; la differenza di $1$ dipende solo da come si contano le potenze di $\omega_n$ (qui si passa anche per $\omega_n^{n/2}$, che serve per ottenere le potenze successive). In ogni caso $T_a(n)=\Theta(n)$.

Miglioramento della costante. Le radici escluse sono $1$ e $-1$, quindi le radici rimaste si raggruppano in coppie $\omega_n^h$ e $\omega_n^{h+n/2}=-\omega_n^h$, per $h=1,\dots,n/2-1$: $$p_n(x)=\prod_{h=1}^{n/2-1}(x-\omega_n^h)(x+\omega_n^h)=\prod_{h=1}^{n/2-1}\bigl(x^2-\omega_n^{2h}\bigr)=\prod_{h=1}^{n/2-1}\bigl(x^2-\omega_{n/2}^h\bigr),$$ dove l'ultimo passaggio è il lemma di cancellazione. Da qui $p_n(-x)=p_n(x)$: il polinomio è pari, quindi $p_n(1)=p_n(-1)$ e basta una sola valutazione, con soli $n/2-1$ fattori $1-\omega_{n/2}^h$. Con le potenze di $\omega_{n/2}$ ottenute di seguito ($n/2-2$ prodotti), i fattori ($n/2-1$ differenze) e gli accumuli ($n/2-2$ prodotti) il costo è $\frac32n-5$ (verificato per $n=4,\dots,64$: $1,7,19,43,91$), cioè $\frac32n+O(1)$.

Osservazione, forma chiusa. Il prodotto di tutti i fattori $(x-\omega_n^h)$, $h=0,\dots,n-1$, è $x^n-1$ (polinomio monico di grado $n$ con le $n$ radici distinte $\omega_n^h$). Quindi $p_n(x)\,(x-1)(x+1)=x^n-1$ e $$p_n(x)=\frac{x^n-1}{x^2-1}=1+x^2+x^4+\dots+x^{n-2}.$$ Per $n=4$: $p_4(x)=(x-i)(x+i)=x^2+1$. Da questa forma si leggono subito $a_i=1$ per $i$ pari con $i\le n-2$, $a_i=0$ per $i$ dispari, e $p_n(1)=p_n(-1)=n/2$ (verificato con numpy per $n=4,8,16,32$; per $n=64$ l'espansione numerica dei fattori perde precisione, ma la formula resta esatta). Il testo però chiede la strada che passa per la DFT, che si applica a qualunque insieme di radici escluse: la si segue qui sotto, usando la forma chiusa solo come controllo.

(b) La complessità è polinomiale?

No. L'input è il numero $n$, scritto in binario con $|\langle n\rangle|=\lfloor\log_2n\rfloor+1$ bit, e la complessità di un algoritmo si dice polinomiale quando è limitata da un polinomio nella taglia dell'input, non nel valore. Da $n\ge2^{|\langle n\rangle|-1}$ segue $$T_a(n)=5n-12\ \ge\ 5\cdot2^{|\langle n\rangle|-1}-12,$$ che è esponenziale nella taglia $|\langle n\rangle|$. Il costo $\Theta(n)$ sembra buono solo se si confonde il valore $n$ con la taglia dell'istanza (come in un algoritmo di primalità che prova tutti i divisori fino a $n$: lineare nel valore, esponenziale nei bit). Anche la versione migliorata, di costo $\frac32n-5$, è esponenziale nella taglia. Con la forma chiusa $p_n(1)=p_n(-1)=n/2$ dell'osservazione in (a), invece, bastano $O(1)$ operazioni.

(c) La DFT dei coefficienti

La DFT di ordine $n$ del vettore dei coefficienti restituisce le valutazioni di $p_n$ sulle radici $n$-esime dell'unità (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à →): $$A_h=p_n(\omega_n^h),\qquad 0\le h\le n-1.$$ Per definizione $p_n$ si annulla in tutte le radici tranne $1=\omega_n^0$ e $-1=\omega_n^{n/2}$. Quindi $A_h=0$ per $h\notin\{0,n/2\}$, $A_0=p_n(1)$, $A_{n/2}=p_n(-1)$, e per la parità $p_n(-1)=p_n(1)=:P$: $$(A_0,\dots,A_{n-1})=(P,0,\dots,0,\underset{\text{posto }n/2}{P},0,\dots,0).$$ Algoritmo: calcolare $P$ (parte (a), versione migliorata) e scrivere il vettore con $P$ nelle posizioni $0$ e $n/2$ e zeri altrove. Scrivere gli $n-2$ zeri non è un'operazione aritmetica. Costo: $T_c(n)=T_a'(n)=\frac32n+O(1)=O(n)$, dove $T_a'$ è il costo della valutazione migliorata. (La soluzione del corso scrive $T_c(n)=T_a(n)=3n-8$, il costo di una valutazione con l'algoritmo non migliorato: lo stesso ordine di grandezza.)

(d) I coefficienti con la DFT inversa

Il vettore dei coefficienti è l'antitrasformata di $(A_h)$. Per la formula dell'inversa ($[F_n^{-1}]_{ih}=\frac1n\omega_n^{-ih}$, vedi 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 →): $$a_i=\frac1n\sum_{h=0}^{n-1}A_h\,\omega_n^{-ih}=\frac1n\Bigl(A_0\,\omega_n^0+A_{n/2}\,\omega_n^{-in/2}\Bigr)=\frac Pn\Bigl(1+(\omega_n^{n/2})^{-i}\Bigr)=\frac Pn\bigl(1+(-1)^{i}\bigr),$$ perché tutti gli altri addendi sono nulli e $\omega_n^{n/2}=-1$ (quindi $(-1)^{-i}=(-1)^i$). Dunque $$a_i=\begin{cases}\dfrac{2P}{n}&i\text{ pari},\\[2mm]0&i\text{ dispari}.\end{cases}$$ In particolare $a_{n-1}=0$ ($n-1$ è dispari), come richiesto dal testo.

Algoritmo: si calcola $P$, poi $q=2P/n$ (una divisione e un prodotto), e si riempie il vettore con $q$ agli indici pari e $0$ a quelli dispari. Correttezza: è la formula appena dimostrata, che discende dal teorema sulla matrice inversa di Fourier e dal fatto che $\mathrm{DFT}_n(\mathbf a)$ è proprio il vettore trovato in (c). Costo: $T_d(n)=\frac32n+O(1)+2=O(n)$, dominato dal calcolo di $P$; le $n$ componenti si scrivono per copia.

Controllo. Con la forma chiusa dell'osservazione, $P=n/2$ e $q=2\cdot\frac n2\cdot\frac1n=1$: i coefficienti pari sono $1$ e quelli dispari $0$, come in $1+x^2+\dots+x^{n-2}$. Per $n=8$: $\mathbf a=(1,0,1,0,1,0,1,0)$ e la DFT è $(4,0,0,0,4,0,0,0)$ (verificato: sommando i coefficienti si ottiene $4=p_8(1)$, e $p_8(-1)=1+1+1+1=4$).

Con i vettori sparsi. Lo stesso risultato segue riconoscendo che $(A_0,\dots,A_{n-1})$ è $(n,n/2)$-sparso (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 →). Per la trasformata inversa, che usa $\omega_n^{-1}$ al posto di $\omega_n$ (stessi lemmi), $\mathrm{FFT\_NEG}$ è fatta di $n/2$ copie della trasformata di ordine $2$ delle componenti non banali $(A_0,A_{n/2})=(P,P)$, cioè di $(P+P,\,P-P)=(2P,0)$ ripetuto $n/2$ volte; dividendo per $n$ si ottiene $(2P/n,0,2P/n,0,\dots)$, lo stesso vettore.