Salta al contenuto
Note per Studenti Esercizio - Algoritmo di Freivalds su matrici 3x3 con elementi sbagliati

Esercizio - Algoritmo di Freivalds su matrici 3x3 con elementi sbagliati

Testo. Siano A=(120312011),B=(201110132).A=\begin{pmatrix}1&2&0\\3&1&2\\0&1&1\end{pmatrix},\quad B=\begin{pmatrix}2&0&1\\1&1&0\\1&3&2\end{pmatrix}. Uno studente propone il prodotto C=(431977242)C=\begin{pmatrix}4&3&1\\9&7&7\\2&4&2\end{pmatrix} e un altro C′=(511977242)C'=\begin{pmatrix}5&1&1\\9&7&7\\2&4&2\end{pmatrix}.

  1. Calcolare ABAB e dire quali elementi di CC e C′C' sono sbagliati.
  2. Eseguire l'algoritmo di Freivalds con r=(1,0,1)Tr=(1,0,1)^T e con r=(0,1,0)Tr=(0,1,0)^T su CC. Ripetere su C′C' con r=(1,1,0)Tr=(1,1,0)^T.
  3. Per tutti gli 88 vettori r∈{0,1}3r\in\{0,1\}^3, contare quelli per cui l'algoritmo non scopre l'errore, per CC e per C′C'. Confrontare con il bound 1/21/2.
  4. Costo per n=1000n=1000 con 2020 prove, e probabilità di errore.

Teoria: Union bound e verifica randomizzata - identità polinomiali e prodotti di matriciSpazi discreti richiamati; inclusione-esclusione (con le troncate di Bonferroni) e union bound Pr[unione] ≤ somma, valido senza indipendenza e stretto quando gli eventi sono rari (collisioni: C(n,2)/m). Principio delle decisioni differite: si fissa tutto tranne una scelta casuale e si limita la probabilità su quella. Lemma di Schwartz-Zippel: un polinomio non nullo di grado totale d, valutato in un punto di S^n scelto uniformemente, si annulla con prob ≤ d/|S| (induzione sul numero di variabili); test di identità polinomiale con errore unilaterale, ripetuto (d/|S|)^k. Freivalds: per verificare AB=C si controlla A(Br)=Cr con r in {0,1}^n in tempo O(n^2), errore ≤ 1/2 (stretto), 2^-k con k prove. Fingerprint: due stringhe di n bit si confrontano con a mod p per un primo casuale p ≤ M, errore ≤ n/π(M).Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici → (sezione 4); 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 →.

Soluzione

Punto 1. Riga per colonna: AB=(1⋅2+2⋅1+0⋅11⋅0+2⋅1+0⋅31⋅1+2⋅0+0⋅23⋅2+1⋅1+2⋅13⋅0+1⋅1+2⋅33⋅1+1⋅0+2⋅20⋅2+1⋅1+1⋅10⋅0+1⋅1+1⋅30⋅1+1⋅0+1⋅2)=(421977242).AB=\begin{pmatrix}1\cdot2+2\cdot1+0\cdot1&1\cdot0+2\cdot1+0\cdot3&1\cdot1+2\cdot0+0\cdot2\\3\cdot2+1\cdot1+2\cdot1&3\cdot0+1\cdot1+2\cdot3&3\cdot1+1\cdot0+2\cdot2\\0\cdot2+1\cdot1+1\cdot1&0\cdot0+1\cdot1+1\cdot3&0\cdot1+1\cdot0+1\cdot2\end{pmatrix}=\begin{pmatrix}4&2&1\\9&7&7\\2&4&2\end{pmatrix}. CC ha un solo elemento sbagliato: C12=3C_{12}=3 (dovrebbe essere 22), quindi D=AB−CD=AB-C ha solo D12=−1D_{12}=-1. C′C' ne ha due, nella prima riga: C11′=5C'_{11}=5 invece di 44 e C12′=1C'_{12}=1 invece di 22, quindi la prima riga di D′=AB−C′D'=AB-C' è (−1, 1, 0)(-1,\,1,\,0).

Punto 2.

  • CC, r=(1,0,1)r=(1,0,1): Br=(2+1, 1+0, 1+2)=(3,1,3)Br=(2+1,\ 1+0,\ 1+2)=(3,1,3), A(Br)=(3+2, 9+1+6, 0+1+3)=(5,16,4)A(Br)=(3+2,\ 9+1+6,\ 0+1+3)=(5,16,4), Cr=(4+1, 9+7, 2+2)=(5,16,4)Cr=(4+1,\ 9+7,\ 2+2)=(5,16,4). Uguali: errore non scoperto.
  • CC, r=(0,1,0)r=(0,1,0): Br=(0,1,3)Br=(0,1,3), A(Br)=(2, 1+6, 1+3)=(2,7,4)A(Br)=(2,\ 1+6,\ 1+3)=(2,7,4), Cr=(3,7,4)Cr=(3,7,4). Diversi: errore scoperto (prima riga).
  • C′C', r=(1,1,0)r=(1,1,0): Br=(2,2,4)Br=(2,2,4), A(Br)=(2+4, 6+2+8, 2+4)=(6,16,6)A(Br)=(2+4,\ 6+2+8,\ 2+4)=(6,16,6), C′r=(5+1, 16, 6)=(6,16,6)C'r=(5+1,\ 16,\ 6)=(6,16,6). Uguali: non scoperto perché D′rD'r ha prima componente −1+1=0-1+1=0.

Punto 3. L'algoritmo sbaglia se e solo se Dr=0Dr=0.

  • CC: Dr=0Dr=0 equivale a −r2=0-r_2=0, cioè r2=0r_2=0: i vettori (0,0,0),(0,0,1),(1,0,0),(1,0,1)(0,0,0),(0,0,1),(1,0,0),(1,0,1), 44 su 88, probabilità 1/21/2. Il bound 1/21/2 è raggiunto (stretto), perché DD ha un solo elemento non nullo.
  • C′C': D′r=0D'r=0 equivale a −r1+r2=0-r_1+r_2=0, cioè r1=r2r_1=r_2: (0,0,0),(0,0,1),(1,1,0),(1,1,1)(0,0,0),(0,0,1),(1,1,0),(1,1,1), 44 su 88, ancora 1/21/2.

In entrambi i casi la probabilità è ≤1/2\le1/2, come dimostra il teorema (si fissano le altre componenti e al più uno dei due valori di rjr_j annulla la somma).

Punto 4. Una prova costa 33 prodotti matrice-vettore, circa 3n2=3⋅1063n^2=3\cdot10^6 operazioni; 2020 prove 6⋅1076\cdot10^7, contro il prodotto diretto ≈n3=109\approx n^3=10^9. L'errore (matrice sbagliata dichiarata giusta) è ≤2−20≈9,5⋅10−7\le2^{-20}\approx9{,}5\cdot10^{-7}; una CC corretta è sempre accettata.

Risultati: AB=(421977242)AB=\begin{pmatrix}4&2&1\\9&7&7\\2&4&2\end{pmatrix}; sfuggono 4/84/8 per CC e 4/84/8 per C′C'; errore con 2020 prove ≤2−20\le2^{-20}.

python
import itertools
A = [[1, 2, 0], [3, 1, 2], [0, 1, 1]]; B = [[2, 0, 1], [1, 1, 0], [1, 3, 2]]
mv = lambda M, v: [sum(M[i][j] * v[j] for j in range(3)) for i in range(3)]
AB = [[sum(A[i][k] * B[k][j] for k in range(3)) for j in range(3)] for i in range(3)]
C = [[4, 3, 1], [9, 7, 7], [2, 4, 2]]; C1 = [[5, 1, 1], [9, 7, 7], [2, 4, 2]]
print(AB)
for nome, M in (("C", C), ("C'", C1)):
    sfuggono = [r for r in itertools.product((0, 1), repeat=3) if mv(A, mv(B, r)) == mv(M, r)]
    print(nome, len(sfuggono), sfuggono)

Versione ripasso

Teoria collegata