Checking Matrix Multiplication three nxn matrices A,B,C: 3.0 na ve 兰 C 2.9 人 O(n) Strassen 2.8 PaⅫ Bini et al. 2.7 gorithm:O(n2.373) 2.6 Schonhage Romani 2.5 Coppersmith,Winograd Strassen 2.4 Coppersmith,Winograd Stothers Williams Year 1950 1960 1970 1980 1990 2000 2010
Checking Matrix Multiplication A × B = C ? three n×n matrices A, B, C: best matrix multiplication algorithm: O(n) O(n2.373)
Checking Matrix Multiplication three nxn matrices A,B,C: A X B 是 C best matrix multiplication algorithm:O(n2.373) Freivald's Algorithm pick a uniform random r E0,1)"; check whether A(Br)=Cr; time:O(n2) if AB =C,always correct
best matrix multiplication algorithm: Checking Matrix Multiplication A × B = C ? three n×n matrices A, B, C: Freivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; time: O(n2) if AB = C, always correct O(n2.373)
Freivald's Algorithm pick a uniform random r∈{0，l"; check whether A(Br)=Cr; if AB =C,always correct ifAB≠C, letD=AB-C≠0n×n sayD,卡0 2n1 1 PABr-C1-PD.s 2 二 -2 m (Dr)i=>Dikrk =0 D r k=1 i ∑D >=D k≠j
Freivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; if AB = C, always correct if AB ≠ C, Pr[ABr = Cr] = Pr[Dr = 0] let D = AB C = 0nn D r i (Dr)i = n k=1 Dikrk =0 rj = 1 Dij n k=j Dikrk 2n 2n1 = 1 2 say Dij = 0
Freivald's Algorithm pick a uniform random r∈{0，l"; check whether A(Br)=Cr; if AB =C,always correct Theorem(Freivald,1979) IfAB≠C,for a uniformly random r∈{0,1n, 1 Pr[ABr=Cr]≤ repeat independently for 100 times time:O(n2) ifAB≠C,error probability≤2-1oo
Freivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; if AB = C, always correct If AB ⇥= C, for a uniformly random r {0, 1}n , Pr[ABr = Cr] 1 2 . Theorem (Freivald, 1979) repeat independently for 100 times time: O(n2) if AB ≠ C, error probability ≤ 2100
Monte Carlo ys Las Vegas Two types of randomized algorithms: Monte Carlo Las Vegas LAS VEGAS N E VA DA running time is fixed always correct correctness is random running time is random
Monte Carlo vs Las Vegas Monte Carlo Las Vegas running time is fixed correctness is random always correct running time is random Two types of randomized algorithms: