Esercizio - matrici ARB, prodotto con tre chiamate ricorsive (compito del 19 giugno 2024, es. 1)

Compito d'esame di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, 19 giugno 2024, seconda parte, esercizio 1 (17 punti). 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 → (stesso schema: meno chiamate, più lavoro nei nodi interni), Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchimodello di costo sulle matrici n x n (operazioni tra scalari, taglia n oppure N = n^2); somma in n^2 operazioni (ottima); prodotto righe per colonne iterativo con costo esatto 2n^3 - n^2; proprietà frattale del prodotto a blocchi dimostrata sugli indici; algoritmo ricorsivo RMUL con T(n) = 8T(n/2) + n^2, Theta(n^3) e soluzione esatta 2n^3 - n^2 per induzione e per srotolamento: fa le stesse operazioni dell'iterativo.Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi →, 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 Dimostrazioni, induzione e invariantiTecniche di dimostrazione (esempio, controesempio, assurdo), induzione con casi base multipli, invarianti di ciclo (inizializzazione, conservazione, uso alla fine), schema generale per provare la correttezza; esempi svolti su arrayMax, sequenza di bit e numeri di Fibonacci.Dimostrazioni, induzione e invarianti →.

Testo

Sia $n \ge 1$ una potenza di $2$. Una matrice $M \in \mathbb C^{n \times n}$ si dice Antisimmetrica Ricorsiva a Blocchi di ordine $n$ (in breve, $n$-ARB) se $n = 1$ oppure se $n \ge 2$ e

$$M = \begin{pmatrix} A & B \\ -B & A \end{pmatrix},$$

dove i blocchi $A$ e $B$ di $M$ sono a loro volta matrici $\frac n2$-ARB.

• Punto 1.(a) [4 punti] Si dimostri induttivamente che, date due matrici $n$-ARB $M$ e $Q$, il loro prodotto $P = MQ$ è una matrice $n$-ARB. Nella dimostrazione, si dia per già dimostrato che la somma e la differenza di due matrici $n$-ARB è una matrice $n$-ARB.
• Punto 1.(b) [8 punti] Si fornisca lo pseudocodice di un algoritmo ricorsivo efficiente ARB_MUL$(M, Q)$ per moltiplicare due matrici $n$-ARB $M$ e $Q$ e se ne argomenti la correttezza. L'algoritmo potrà usare (senza che ne venga descritto il codice) le subroutine ARB_SUM$(U, V)$, ARB_SUB$(U, V)$ e ARB_SCALPROD$(a, U)$ per il calcolo, rispettivamente, di $U + V$, $U - V$ e $a \cdot U$, dove $U$ e $V$ sono ARB dello stesso ordine e $a \in \mathbb C$.
• Punto 1.(c) [5 punti] Supponendo che, per matrici $n$-ARB, $T_{ARB\_SUM}(n) = T_{ARB\_SUB}(n) = T_{ARB\_SCALPROD}(n) = n$, si scriva l'equazione di ricorrenza per il numero esatto $T_{ARB\_MUL}(n)$ di operazioni aritmetiche tra scalari complessi effettuate dall'algoritmo sviluppato per il punto 1.(b) e se ne determini l'ordine di grandezza con il Master Theorem.

Attenzione: per avere punteggio pieno, l'algoritmo al punto 1.(b) dovrà avere complessità $o(n^2)$. (Suggerimento: si cerchi una proprietà di sottostruttura con solo tre prodotti ricorsivi.)

Come si legge la struttura

Una $n$-ARB è fatta con due blocchi ripetuti, $A$ e $B$, con $B$ che compare anche cambiato di segno: ha $n$ valori indipendenti. Per $n = 2$ e $n = 4$:

$$M = \begin{pmatrix} a & b \\ -b & a \end{pmatrix}, \qquad M = \begin{pmatrix} a & b & c & d \\ -b & a & -d & c \\ -c & -d & a & b \\ d & -c & -b & a \end{pmatrix}$$

con $A = \begin{pmatrix} a & b \\ -b & a \end{pmatrix}$ e $B = \begin{pmatrix} c & d \\ -d & c \end{pmatrix}$. La somiglianza con i numeri complessi $a + ib$ è utile: $\begin{pmatrix} a & b \\ -b & a \end{pmatrix}$ si moltiplica come $a + ib$ (con $i^2 = -1$), e la ricorsione porta a "numeri complessi a coefficienti ARB". Il trucco dei tre prodotti è quello di Gauss per il prodotto complesso.

Punto (a): chiusura per prodotto

Induzione su $k \ge 0$ con $n = 2^k$. Base ($n = 1$): ogni scalare complesso è $1$-ARB e il prodotto di due scalari è uno scalare. Ipotesi: il prodotto di due matrici $\frac n2$-ARB è $\frac n2$-ARB. Passo: siano $M, Q$ $n$-ARB con $n > 1$,

$$M = \begin{pmatrix} A & B \\ -B & A \end{pmatrix}, \qquad Q = \begin{pmatrix} C & D \\ -D & C \end{pmatrix}, \quad A, B, C, D \; \tfrac n2\text{-ARB}.$$

Per la proprietà frattale del prodotto righe per colonne (Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchimodello di costo sulle matrici n x n (operazioni tra scalari, taglia n oppure N = n^2); somma in n^2 operazioni (ottima); prodotto righe per colonne iterativo con costo esatto 2n^3 - n^2; proprietà frattale del prodotto a blocchi dimostrata sugli indici; algoritmo ricorsivo RMUL con T(n) = 8T(n/2) + n^2, Theta(n^3) e soluzione esatta 2n^3 - n^2 per induzione e per srotolamento: fa le stesse operazioni dell'iterativo.Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi →), ogni quadrante di $MQ$ è somma di due prodotti dei quadranti di $M$ (riga) e di $Q$ (colonna):

$$MQ = \begin{pmatrix} AC + B(-D) & AD + BC \\ (-B)C + A(-D) & (-B)D + AC \end{pmatrix} = \begin{pmatrix} AC - BD & AD + BC \\ -BC - AD & -BD + AC \end{pmatrix} = \begin{pmatrix} E & F \\ -F & E \end{pmatrix}$$

con $E = AC - BD$ e $F = AD + BC$ (nel quadrante in basso a sinistra $-BC - AD = -(AD + BC) = -F$ perché la somma delle matrici è commutativa; in basso a destra $-BD + AC = E$). Poiché $A, B, C, D$ sono $\frac n2$-ARB, per ipotesi induttiva i quattro prodotti $AC, BD, AD, BC$ sono $\frac n2$-ARB; allora $E$ (differenza) e $F$ (somma) sono $\frac n2$-ARB per la chiusura per somma e differenza, che si può assumere. Quindi $MQ$ ha la forma $\begin{pmatrix} E & F \\ -F & E \end{pmatrix}$ con $E, F$ $\frac n2$-ARB: è $n$-ARB. $\blacksquare$

Punto (b): algoritmo con tre prodotti ricorsivi

Dalla dimostrazione, $P = MQ = \begin{pmatrix} E & F \\ -F & E \end{pmatrix}$ con $E = AC - BD$ e $F = AD + BC$. Calcolarli con la definizione richiede quattro prodotti $\frac n2$-ARB ($AC, BD, AD, BC$) e quindi $T(n) = 4T(\frac n2) + \Theta(n)$, soglia $n^2$, caso 1: $\Theta(n^2)$, non $o(n^2)$. Servono tre prodotti (suggerimento). Si pongono

$$U = AC, \qquad V = BD, \qquad Z = (A + B)(C + D) = AC + AD + BC + BD,$$

e si osserva che $E = AC - BD = U - V$ e, dall'espansione di $Z$, $F = AD + BC = Z - AC - BD = Z - U - V$. Con $A + B$ e $C + D$ ARB per la chiusura per somma. Tre prodotti ricorsivi ($U$, $V$, $Z$) invece di quattro, con più somme e sottrazioni (è il trucco di Gauss per il prodotto complesso).

ARB_MUL(M, Q)                 { M, Q ARB dello stesso ordine n }
  n <- rows(M)
  if n = 1 then return [m11 * q11]
  * M = [A B; -B A],  Q = [C D; -D C] *
  U <- ARB_MUL(A, C)
  V <- ARB_MUL(B, D)
  Z <- ARB_MUL(ARB_SUM(A, B), ARB_SUM(C, D))
  E <- ARB_SUB(U, V)
  F <- ARB_SUB(Z, ARB_SUM(U, V))
  Fn <- ARB_SCALPROD(-1, F)
  return [E F; Fn E]

Correttezza. Per induzione su $k$: per $n = 1$ restituisce il prodotto degli scalari. Per $n > 1$, $A, B, C, D$ sono ARB per definizione e le somme $A + B$, $C + D$ sono ARB (il testo dà per dimostrata la chiusura per somma), quindi le tre chiamate ricorsive sono legittime (input ARB dello stesso ordine) e per ipotesi restituiscono $U = AC$, $V = BD$, $Z = (A + B)(C + D)$. Le identità $E = U - V$ e $F = Z - (U + V)$ sono quelle mostrate sopra, e la matrice restituita $\begin{pmatrix} E & F \\ -F & E \end{pmatrix}$ coincide con $MQ$ per il punto (a); la parte in basso a sinistra è $-F$, ottenuta con ARB_SCALPROD$(-1, F)$.

Punto (c): ricorrenza e Master Theorem

Per $n = 1$: una moltiplicazione tra scalari, $T(1) = 1$. Per $n > 1$: tre chiamate ricorsive su ordine $\frac n2$ e sei invocazioni di subroutine su matrici ARB di ordine $\frac n2$, ciascuna di costo $\frac n2$ (perché $T_{ARB\_SUM}(\frac n2) = \frac n2$ e analogamente le altre):

Lavoro: $6 \cdot \frac n2 = 3n$. La ricorrenza è

$$T_{ARB\_MUL}(n) = \begin{cases} 1 & n = 1, \\ 3\,T_{ARB\_MUL}\!\left(\frac n2\right) + 3n & n > 1. \end{cases}$$

Master Theorem (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 →): $a = 3$, $b = 2$, soglia $n^{\log_2 3} \approx n^{1.585}$. Esiste $\varepsilon > 0$ con $w(n) = 3n = O(n^{\log_2 3 - \varepsilon})$ (per esempio $\varepsilon = 0.5$, perché $1 \le 1.585 - 0.5$): caso 1, $T_{ARB\_MUL}(n) = \Theta(n^{\log_2 3}) = o(n^2)$.

Soluzione esatta (non richiesta, ma utile come controllo). Con la formula generale: livello $\ell$ ha $3^\ell$ nodi su taglia $\frac{n}{2^\ell}$ con lavoro $3 \frac{n}{2^\ell}$, foglie $3^k$:

$$T(n) = \sum_{\ell=0}^{k-1} 3^\ell \cdot \frac{3n}{2^\ell} + 3^k = 3n \cdot 2\left( \left(\tfrac 32\right)^k - 1 \right) + 3^k = 6 \cdot 3^k - 6n + 3^k = 7 \cdot 3^k - 6 \cdot 2^k = 7n^{\log_2 3} - 6n.$$

Controllo: $n = 1$ dà $1$; $n = 2$ dà $21 - 12 = 9$: tre prodotti di scalari ($ac$, $bd$, $(a + b)(c + d)$) e $6$ operazioni (due somme per $a + b$ e $c + d$, $e = u - v$, $u + v$, $z - (u + v)$, e il cambio di segno contato dal testo), $3 + 6 = 9$ ✓. Se invece si considerasse gratis il cambio di segno si avrebbe $\frac 52 n$ di lavoro e $T(n) = 6 \cdot 3^k - 5 \cdot 2^k$.

Esempio ($n = 2$). $M = \begin{pmatrix} 1 & 2 \\ -2 & 1 \end{pmatrix}$, $Q = \begin{pmatrix} 3 & 1 \\ -1 & 3 \end{pmatrix}$: $A = 1$, $B = 2$, $C = 3$, $D = 1$. $U = 3$, $V = 2$, $Z = (1 + 2)(3 + 1) = 12$, $E = 3 - 2 = 1$, $F = 12 - 5 = 7$. Quindi $MQ = \begin{pmatrix} 1 & 7 \\ -7 & 1 \end{pmatrix}$. Controllo con la definizione: $\begin{pmatrix} 1 \cdot 3 + 2 \cdot (-1) & 1 \cdot 1 + 2 \cdot 3 \\ -2 \cdot 3 + 1 \cdot (-1) & -2 \cdot 1 + 1 \cdot 3 \end{pmatrix} = \begin{pmatrix} 1 & 7 \\ -7 & 1 \end{pmatrix}$ ✓.

Verifica con un programma. Un'implementazione di ARB_MUL sulla prima riga $(A \,|\, B)$, con conteggio delle operazioni e confronto con il prodotto delle matrici piene, per $n = 1, \dots, 128$, dà $T(n) = 7 \cdot 3^k - 6 \cdot 2^k$, coerente con la ricorrenza $3T(\frac n2) + 3n$.