Esercizio - matrice V per V trasposta con V di Vandermonde, formula degli elementi e calcolo in tempo quadratico (compito del 4 settembre 2024, es. 2)

Teoria usata: 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 → (matrice di Vandermonde), Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica → e SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie → (somma di una progressione geometrica), Esponenziazione veloce per quadrature successivepotenza x^n con un operatore associativo con elemento neutro, costo = numero di applicazioni dell'operatore; STUPID_POWER costa n-1, la sottostruttura x^n = (x^floor(n/2))^2 (per n dispari per x) dà POWER con T(n) = floor(log2 n) + (numero di bit a 1 di n) - 1, Theta(log n) (caso peggiore 2 floor(log2 n), n = 2^t - 1); versioni iterative POWER2 e POWER3 dalla rappresentazione binaria di n; esempio con la matrice di Fibonacci; il modello a costo unitario vale solo se l'operatore non fa crescere gli operandi.Esponenziazione veloce per quadrature successive → (potenza in $O(\log n)$ prodotti), Operazioni tra matriciLe matrici m×n formano uno spazio vettoriale (somma e prodotto per scalare elemento per elemento); il prodotto righe per colonne corrisponde alla composizione di funzioni lineari, è associativo ma non commutativo; la trasposta scambia righe e colonne e (AB)^T = B^T A^T.Operazioni tra matrici → (prodotto righe per colonne).

Nessun elemento di $W$ richiede di moltiplicare matrici: la struttura di Vandermonde trasforma ogni elemento in una somma geometrica di ragione $x_ix_j$.

(a) La formula di $W_{ij}$

Per definizione di prodotto righe per colonne, con $(V^T)_{kj}=V_{jk}=x_j^k$: $$W_{ij}=\sum_{k=0}^{n-1}V_{ik}\,(V^T)_{kj}=\sum_{k=0}^{n-1}V_{ik}V_{jk}=\sum_{k=0}^{n-1}x_i^k\,x_j^k=\sum_{k=0}^{n-1}(x_ix_j)^k.$$ Posto $b=x_ix_j$, è la somma dei primi $n$ termini della progressione geometrica di ragione $b$ (Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica →, valida in $\mathbb C$). Due casi:

• se $b=1$ ogni termine vale $1$ e la somma è $n$;
• se $b\ne1$ la formula chiusa è $\dfrac{b^n-1}{b-1}$ (infatti $(b-1)\sum_{k<n}b^k=b^n-1$ per telescopia).

$$W_{ij}=\begin{cases}n&x_ix_j=1,\\[2mm]\dfrac{(x_ix_j)^n-1}{x_ix_j-1}&x_ix_j\ne1.\end{cases}$$ Il caso $x_ix_j=1$ va trattato a parte perché la formula chiusa darebbe $\frac00$. La matrice $W$ è simmetrica, $W_{ij}=W_{ji}$, perché $x_ix_j=x_jx_i$.

Esempio ($n=3$, $\mathbf x=(2,\tfrac12,3)$). $V=\begin{pmatrix}1&2&4\\1&\frac12&\frac14\\1&3&9\end{pmatrix}$. Gli elementi: $W_{00}$: $b=4$, $\frac{4^3-1}{4-1}=21$ (infatti $1+4+16=21$); $W_{01}$: $b=2\cdot\frac12=1$, quindi $W_{01}=n=3$ (infatti $1+1+1$); $W_{02}$: $b=6$, $\frac{216-1}{5}=43$ ($1+6+36$); $W_{11}$: $b=\frac14$, $\frac{1/64-1}{1/4-1}=\frac{21}{16}$; $W_{12}$: $b=\frac32$, $\frac{27/8-1}{1/2}=\frac{19}4$; $W_{22}$: $b=9$, $\frac{729-1}{8}=91$. Quindi $$W=\begin{pmatrix}21&3&43\\3&\frac{21}{16}&\frac{19}{4}\\43&\frac{19}{4}&91\end{pmatrix},$$ uguale a $VV^T$ calcolato per righe per colonne (controllo fatto anche con numpy su valori complessi casuali con un elemento forzato a $x_ix_j=1$).

(b) Valutare un singolo elemento in $O(\log n)$

Si calcola $b=x_ix_j$; se $b=1$ si restituisce $n$, altrimenti si restituisce $\bigl(b^n-1\bigr)/(b-1)$ con la potenza per quadrature successive.

EVAL_W(x, i, j)
n <- x.len
b <- x[i] * x[j]
if b = 1 then return n
else return (POWER(b, n) - 1) / (b - 1)

POWER(b, n) esegue $\lfloor\log_2n\rfloor$ quadrature e $\mathrm{popcount}(n)-1$ prodotti per le cifre $1$ dell'esponente (verificato contando i prodotti di un'implementazione, per esempio $n=13$: $3+3-1=5$ prodotti; $n=100$: $6+3-1=8$), in ogni caso al più $2\lfloor\log_2n\rfloor$. Le altre operazioni sono $1$ prodotto ($b$), $2$ sottrazioni e $1$ divisione. Quindi $$T_{el}\le2\lfloor\log_2n\rfloor+4=O(\log n),$$ e calcolare tutti gli $n^2$ elementi con questo algoritmo costa $O(n^2\log n)$ (il confronto $b=1$ è un test, non un'operazione aritmetica).

(c) L'intera matrice in $O(n^2)$

Il costo $\log n$ per elemento viene dalla potenza $(x_ix_j)^n$. Ma $$(x_ix_j)^n=x_i^n\cdot x_j^n,$$ cioè dipende da $i$ e da $j$ separatamente, e le $n^2$ potenze richieste sono prodotti delle sole $n$ potenze $y_i=x_i^n$. Si calcolano allora una volta sola $\mathbf y=(x_0^n,\dots,x_{n-1}^n)$, e ogni elemento costa un numero costante di operazioni: $$W_{ij}=\begin{cases}n&x_ix_j=1,\\[1mm]\dfrac{y_iy_j-1}{x_ix_j-1}&\text{altrimenti.}\end{cases}$$

COMPUTE_W(x)
n <- x.len
for i <- 0 to n-1
    y[i] <- POWER(x[i], n)              { n chiamate, O(log n) l'una }
for i <- 0 to n-1
    for j <- 0 to n-1
        b <- x[i] * x[j]
        if b = 1 then W[i][j] <- n
        else W[i][j] <- (y[i]*y[j] - 1) / (b - 1)
return W

Costo. Primo ciclo: $n$ potenze, ciascuna al più $2\lfloor\log_2n\rfloor$ prodotti, in tutto $O(n\log n)$. Secondo doppio ciclo: ciascuno degli $n^2$ elementi richiede $b$ ($1$ prodotto), $y_iy_j$ ($1$ prodotto), $y_iy_j-1$ e $b-1$ ($2$ sottrazioni) e una divisione: $5$ operazioni al più (solo $1$ se $b=1$). Totale $$T(n)\le5n^2+2n\lfloor\log_2n\rfloor=O(n^2)\quad(\text{perché }n\log n=O(n^2)).$$ Verificato contando le operazioni di un'implementazione per $n=2,4,5,8$: la parte dopo il precalcolo vale $5n^2$ meno $4$ per ogni elemento con $b=1$ (per $n=2$ con $x_1=1/x_0$, i due elementi $W_{01}$ e $W_{10}$ costano $1$ operazione invece di $5$, quindi $12=20-8$). Sfruttando la simmetria si calcolano solo gli elementi con $j\ge i$ ($n(n+1)/2$) e si copiano gli altri: $\frac52n(n+1)+O(n\log n)$. Il costo $\Theta(n^2)$ è ottimo, perché la matrice ha $n^2$ elementi da scrivere.