Advanced Algorithms Fingerprinting 尹一通Nanjing University,2022Fall
尹⼀通 Nanjing University, 2022 Fall Advanced Algorithms Fingerprinting
Checking Matrix Multiplication three n x n matrices A,B,C: A X B 是 C
• three n × n matrices A, B,C: Checking Matrix Multiplication A × B = C ?
Matrix Multiplication Algorithms n Xn matrix Running time:O(n) 2.9 Year 0 Authors Strassen apovani,Romani,Lotti 1969 2.8074 Strassen 28 1978 2.796 Pan 1979 2.780 Bini,Capovani,Romani 1981 2.522 Schonhage 1981 2.517 Romani 1981 2.496 Coppersmith,Winograd 1986 2.479 Strassen ■g年市n车a年 1990 2.3755 26 Coppersmith,Winograd 2010 2.3737 Stothers Romani smith, 2013 2.3729 Williams Copp ssen 2014 2.3728639 Le Gall 2.5 age 2020 2.3728596 Alman,Williams 2.4 Coppersmith.Winograd 1970 1975 1980 1985 1990 1995 2000 2005 2010 2015 2020 Year
Matrix Multiplication Algorithms matrix Running time: n × n O(nω) Year ω Authors 1969 2.8074 Strassen 1978 2.796 Pan 1979 2.780 Bini, Capovani, Romani 1981 2.522 Schönhage 1981 2.517 Romani 1981 2.496 Coppersmith, Winograd 1986 2.479 Strassen 1990 2.3755 Coppersmith, Winograd 2010 2.3737 Stothers 2013 2.3729 Williams 2014 2.3728639 Le Gall 2020 2.3728596 Alman, Williams
Checking Matrix Multiplication three n xn matrices A,B,C: A X B 名 C Freivald's Algorithm: pick a uniform random r∈{0，l}n; check whether A(Br)=Cr; time:O(n2) if AB C:always correct ifAB≠C:
• three n × n matrices A, B,C: Checking Matrix Multiplication A × B = C ? Freivald’s Algorithm: pick a uniform random ; check whether ; r ∈ {0,1}n A(Br) = Cr time: O(n if AB = C: always correct 2 ) if AB ≠ C:
Freivald's Algorithm: pick a uniform random r∈{0，l}, check whether A(Br)=Cr; fAB≠C: letD=AB-C卡0xn suppose Dii卡0 1 Pr[ABr =Cr]=Pr[Dr=0]< 三 2 (Dr,=∑D4=0 D r k=1 i 之2
Freivald’s Algorithm: pick a uniform random ; check whether ; r ∈ {0,1}n A(Br) = Cr if AB ≠ C: let D = AB − C ≠ 0n×n D r i suppose Dij ≠ 0 Pr[ABr = Cr] = Pr[Dr = 0] ≤ (Dr)i = n ∑ k=1 Dikrk = 0 rj = − 1 Dij ∑ k≠j Dikrk = 1 2 2 n 2n−1