Esercizio - algoritmo di Strassen sulle matrici supercircolanti (esercizi su supercircolanti e circolanti, es. SC 6)

Esercizio supplementare 6 sulle matrici supercircolanti, dalle note ed esercizi del corso di Algoritmi per l'Ingegneria (Ing. Informatica UniPD) su supercircolanti e circolanti. Teoria usata: Algoritmo di Strassen e ibridazioneStrassen calcola il prodotto n x n con 7 chiamate ricorsive invece di 8, usando 10 somme/sottrazioni nel divide e 8 nel conquer: T(n) = 7T(n/2) + (9/2)n^2, Theta(n^(log2 7)) con soluzione esatta 7n^(log2 7) - 6n^2; la costante 7 è più che tripla di quella dell'iterativo (2) e Strassen batte l'iterativo solo da n = 655 (per le potenze di 2, da 1024). L'ibridazione cambia il caso base (iterativo per n <= n0): costo n^(log2 7)(2n0+5)/n0^(log2 7 - 2) - 6n^2, minimo per n0 = 8 con costante ~3.92.Algoritmo di Strassen e ibridazione →, Matrici circolanti e supercircolanti - algoritmi divide and conquerle matrici supercircolanti (quadranti alternati ricorsivi) hanno solo n valori distinti: somma in n operazioni, prodotto in 4n log2 n + n con il trucco (A1+A2)(B1+B2) e (A1-A2)(B1-B2) invece delle 4 chiamate (Theta(n^2)); gli autovalori sono la trasformata di Hadamard della prima riga (FHT, n log2 n) e il prodotto passa dalla base diagonalizzante; le matrici circolanti sono polinomi nella matrice di rotazione R, il loro prodotto è la convoluzione ciclica delle prime righe e si diagonalizzano con la matrice di Fourier: prodotto in O(n log n) con la FFT.Matrici circolanti e supercircolanti - algoritmi divide and conquer →, Master Theorem - enunciato, casi e applicazioniMaster Theorem per T(n) = aT(n/b) + w(n): si confronta w(n) con la funzione soglia n^(log_b a). Caso 1 (w minore di una potenza polinomiale): Theta(n^(log_b a)); caso 2 (w della stessa taglia): Theta(n^(log_b a) log n); caso 3 (w maggiore e regolare): Theta(w(n)). Prova completa dai livelli dell'albero, versione estesa (parti intere, n0 qualsiasi), esempi, e l'uso scorretto quando nessun caso si applica (w = n log n).Master Theorem - enunciato, casi e applicazioni → e Albero della ricorrenza e formula generale per le ricorrenzeL'albero della ricorrenza ha la forma dell'albero delle chiamate dell'istanza peggiore e T(n) è la somma dei lavori dei nodi. Per la famiglia T(n) = s(n)T(f(n)) + w(n) con base T0 per n <= n0, contando i nodi per livello con le iterate di f e il livello f(n,n0) si ottiene la formula chiusa T(n) = somma_l [prodotto_j s(f^(j)(n))] w(f^(l)(n)) + [prodotto s] T0, verificata per induzione e applicata a esempi (merge sort, Hanoi, ricorrenze con radice).Albero della ricorrenza e formula generale per le ricorrenze →.*

Testo

Strassen SC. Si analizzi come si semplifica la proprietà di sottostruttura dell'algoritmo di Strassen quando le matrici da moltiplicare sono supercircolanti (SC). Suggerimenti:

• Onde evitare confusione tra i blocchi delle SC e i fattori $\frac n2 \times \frac n2$ predisposti da Strassen in fase di divide, si denotino questi ultimi come $S_i$ e $D_i$ ($i = 1, 2, \dots, 7$) invece che come $A_i$ e $B_i$ (notazione delle dispense).
• Le semplificazioni possono derivare, in fase di divide, dall'uguaglianza (talvolta a meno del segno) dei fattori, ma anche in fase di conquer, considerando che la matrice prodotto deve essere SC.

Si analizzi il numero di operazioni di un algoritmo per moltiplicare matrici SC basato sulla proprietà di sottostruttura come da voi semplificata. L'algoritmo ottenuto è competitivo con quello $O(n \log_2 n)$?

Punto di partenza

Per due SC $A = \begin{pmatrix} A_1 & A_2 \\ A_2 & A_1 \end{pmatrix}$ e $B = \begin{pmatrix} B_1 & B_2 \\ B_2 & B_1 \end{pmatrix}$ i quadranti sono

$$A_{11} = A_{22} = A_1, \quad A_{12} = A_{21} = A_2, \qquad B_{11} = B_{22} = B_1, \quad B_{12} = B_{21} = B_2.$$

Si riscrivono le formule di Strassen (Algoritmo di Strassen e ibridazioneStrassen calcola il prodotto n x n con 7 chiamate ricorsive invece di 8, usando 10 somme/sottrazioni nel divide e 8 nel conquer: T(n) = 7T(n/2) + (9/2)n^2, Theta(n^(log2 7)) con soluzione esatta 7n^(log2 7) - 6n^2; la costante 7 è più che tripla di quella dell'iterativo (2) e Strassen batte l'iterativo solo da n = 655 (per le potenze di 2, da 1024). L'ibridazione cambia il caso base (iterativo per n <= n0): costo n^(log2 7)(2n0+5)/n0^(log2 7 - 2) - 6n^2, minimo per n0 = 8 con costante ~3.92.Algoritmo di Strassen e ibridazione →) con $S_i$ e $D_i$ al posto di $A_i$ e $B_i$ dei fattori:

$$P_i = S_i \times D_i, \quad C_{11} = P_1 + P_2 - P_4 + P_6, \quad C_{12} = P_4 + P_5, \quad C_{21} = P_6 + P_7, \quad C_{22} = P_2 - P_3 + P_5 - P_7,$$

con $S_1 = A_{12} - A_{22}$, $S_2 = A_{11} + A_{22}$, $S_3 = A_{11} - A_{21}$, $S_4 = A_{11} + A_{12}$, $S_5 = A_{11}$, $S_6 = A_{22}$, $S_7 = A_{21} + A_{22}$, e $D_1 = B_{21} + B_{22}$, $D_2 = B_{11} + B_{22}$, $D_3 = B_{11} + B_{12}$, $D_4 = B_{22}$, $D_5 = B_{12} - B_{22}$, $D_6 = B_{21} - B_{11}$, $D_7 = B_{11}$.

Semplificazione del divide

Sostituendo i quadranti SC:

Si leggono quattro uguaglianze:

• $S_1 = -S_3$ e $D_1 = D_3$, quindi $P_1 = -P_3$ (uguaglianza a meno del segno);
• $S_5 = S_6$ e $D_5 = D_6$, quindi $P_5 = P_6$;
• $S_4 = S_7$ e $D_4 = D_7$, quindi $P_4 = P_7$;
• $S_2 = 2A_1$ e $D_2 = 2B_1$, quindi $P_2 = 4\,A_1B_1$.

I sette prodotti si riducono a quattro prodotti distinti, di matrici SC di ordine $\frac n2$ (i fattori sono somme e differenze di SC, quindi SC):

$$Q_1 = (A_1 - A_2)(B_1 + B_2), \quad Q_2 = A_1B_1, \quad Q_4 = (A_1 + A_2)B_1, \quad Q_5 = A_1(B_2 - B_1),$$

con $P_1 = -Q_1$, $P_3 = Q_1$, $P_2 = 4Q_2$, $P_4 = P_7 = Q_4$, $P_5 = P_6 = Q_5$. Per i fattori servono $4$ operazioni su SC di ordine $\frac n2$: $A_1 - A_2$, $B_1 + B_2$, $A_1 + A_2$, $B_2 - B_1$ (i fattori $A_1$ e $B_1$ sono blocchi, senza costo). Sono $4 \cdot \frac n2 = 2n$ operazioni di divide, contro le $10 \cdot \frac{n^2}{4}$ di Strassen generale.

Semplificazione del conquer

$$C_{11} = P_1 + P_2 - P_4 + P_6 = -Q_1 + 4Q_2 - Q_4 + Q_5, \qquad C_{12} = P_4 + P_5 = Q_4 + Q_5, \qquad C_{21} = P_6 + P_7 = Q_5 + Q_4,$$

$$C_{22} = P_2 - P_3 + P_5 - P_7 = 4Q_2 - Q_1 + Q_5 - Q_4.$$

Poiché il prodotto di due SC è SC, i due quadranti uguali sono $C_1 = C_{11} = C_{22}$ e $C_2 = C_{12} = C_{21}$; le formule lo confermano: $C_{12} = C_{21} = Q_4 + Q_5$ e $C_{11} = C_{22} = -Q_1 + 4Q_2 - Q_4 + Q_5$. Basta calcolare due matrici:

$$C_1 = -Q_1 + 4Q_2 - Q_4 + Q_5, \qquad C_2 = Q_4 + Q_5.$$

Controllo con la definizione ($C_1 = A_1B_1 + A_2B_2$, $C_2 = A_1B_2 + A_2B_1$): $Q_4 + Q_5 = A_1B_1 + A_2B_1 + A_1B_2 - A_1B_1 = A_2B_1 + A_1B_2 = C_2$ ✓; e, sviluppando, $-Q_1 + 4Q_2 - Q_4 + Q_5 = -(A_1B_1 + A_1B_2 - A_2B_1 - A_2B_2) + 4A_1B_1 - (A_1B_1 + A_2B_1) + (A_1B_2 - A_1B_1) = A_1B_1(-1 + 4 - 1 - 1) + A_1B_2(-1 + 1) + A_2B_1(1 - 1) + A_2B_2 = A_1B_1 + A_2B_2 = C_1$ ✓.

Algoritmo e conteggio

S_STRASSEN(A, B)              { A, B SC di ordine n = 2^k }
  n <- rows(A)
  if n = 1 then return [a11 * b11]
  * A = [A1 A2; A2 A1],  B = [B1 B2; B2 B1] *
  Q1 <- S_STRASSEN(S_SUB(A1, A2), S_SUM(B1, B2))
  Q2 <- S_STRASSEN(A1, B1)
  Q4 <- S_STRASSEN(S_SUM(A1, A2), B1)
  Q5 <- S_STRASSEN(A1, S_SUB(B2, B1))
  C1 <- S_SUM( S_SUB( S_SUB( S_SCALPROD(4, Q2), Q1), Q4), Q5)
  C2 <- S_SUM(Q4, Q5)
  return [C1 C2; C2 C1]

Operazioni sui nodi interni, ciascuna su SC di ordine $\frac n2$ (costo $\frac n2$, vedi Matrici circolanti e supercircolanti - algoritmi divide and conquerle matrici supercircolanti (quadranti alternati ricorsivi) hanno solo n valori distinti: somma in n operazioni, prodotto in 4n log2 n + n con il trucco (A1+A2)(B1+B2) e (A1-A2)(B1-B2) invece delle 4 chiamate (Theta(n^2)); gli autovalori sono la trasformata di Hadamard della prima riga (FHT, n log2 n) e il prodotto passa dalla base diagonalizzante; le matrici circolanti sono polinomi nella matrice di rotazione R, il loro prodotto è la convoluzione ciclica delle prime righe e si diagonalizzano con la matrice di Fourier: prodotto in O(n log n) con la FFT.Matrici circolanti e supercircolanti - algoritmi divide and conquer →):

• divide: $4$ (le due differenze $A_1 - A_2$, $B_2 - B_1$ e le due somme $B_1 + B_2$, $A_1 + A_2$);
• conquer: $\mathrm{S\_SCALPROD}(4, Q_2)$, due sottrazioni e una somma per $C_1$, e una somma per $C_2$: $5$.

Totale $9 \cdot \frac n2 = \frac 92 n$:

$$T(n) = \begin{cases} 1 & n = 1, \\ 4\,T\!\left(\frac n2\right) + \frac 92 n & n > 1. \end{cases}$$

Master Theorem: $a = 4$, $b = 2$, soglia $n^{\log_2 4} = n^2$; $w(n) = \frac 92 n = O(n^{2 - \varepsilon})$ con $\varepsilon = 1$: caso 1, $T(n) = \Theta(n^2)$.

Soluzione esatta (formula generale): il livello $\ell$ ha $4^\ell$ nodi su taglia $\frac{n}{2^\ell}$ con lavoro $\frac 92 \frac{n}{2^\ell}$, le foglie sono $4^k = n^2$:

$$T(n) = \sum_{\ell=0}^{k-1} 4^\ell \cdot \frac 92 \frac{n}{2^\ell} + 4^k = \frac 92 n \sum_{\ell=0}^{k-1} 2^\ell + n^2 = \frac 92 n (n - 1) + n^2 = \frac{11}{2} n^2 - \frac 92 n.$$

Controllo: $n = 1$ dà $1$; $n = 2$ dà $22 - 9 = 13$ (quattro prodotti di scalari, più $9$ operazioni).

Conclusione: è competitivo?

No. La semplificazione toglie tre dei sette prodotti, ma ne restano quattro: $a = 4$ e la soglia resta $n^2$, quindi $T(n) = \Theta(n^2)$, contro $\Theta(n \log n)$ dell'algoritmo con $U = (A_1 + A_2)(B_1 + B_2)$ e $V = (A_1 - A_2)(B_1 - B_2)$ ($T = 4n\log_2 n + n$, due sole chiamate). Anzi, la costante è peggiore anche del metodo con quattro chiamate dalla definizione ($T = 2n^2 - n$): $\frac{11}{2} n^2$ contro $2n^2$. Il motivo è che Strassen generale elimina una moltiplicazione sfruttando combinazioni delle sottomatrici in generale distinte; qui la ripetizione dei quadranti $A_{11} = A_{22}$ ecc. fa collassare i sette prodotti a quattro, ma non basta per arrivare a due prodotti, che sono quelli che bastano per le SC ($U$ e $V$ determinano i due quadranti distinti). Per esempio per $n = 1024$: $\frac{11}{2} \cdot 1024^2 - \frac 92 \cdot 1024 = 5\,762\,560$ operazioni contro $4 \cdot 1024 \cdot 10 + 1024 = 41\,984$ di S_MUL.

Verifica con un programma. Un'implementazione di S_STRASSEN sulle prime righe, con conteggio delle operazioni, confrontata con il prodotto delle matrici SC piene per $n = 1, 2, \dots, 128$, dà il prodotto corretto e il conteggio $\frac{11}{2} n^2 - \frac 92 n$; e le uguaglianze $P_5 = P_6$, $P_1 = -P_3$, $P_4 = P_7$ valgono su matrici SC casuali di ordine $4$.