Muszę zaimplementować tzw. szybkie algorytmy mnożenia macierzy. Strassen jest wystarczająco dobrze opisany że bez problemu go zrozumiałem, ale jako drugi algorytm przypadł mi Coppersmith-winograd od dawna próbuję go zrozumieć. Niestety bez większych sukcesów. Czy mógłby ktoś na przykładzie opisać mi działanie tego algorytmu, albo chociaż podać źródła, gdzie mógłbym takie coś znaleźć?-- 3 wrz 2016, o 16:12 --Znalazłem coś takiego :
Kod: Zaznacz cały
#
# 2x2 SOlution of Winograd
#
# s1:=a21+a22;
# s2:=s1-a11;
# s3:=a11-a21;
# s4:=a12-s2;
# s5:=b12-b11;
# s6:=b22-s5;
# s7:=b22-b12;
# s8:=s6-b21;
# p1:=s2*s6;
p1 := (-a11 + a21 + a22) * (b11 - b12 + b22);
p2 := a11 * b11;
p3 := a12 * b21;
# p4:=s3*s7;
p4 := (a11 - a21) * (-b12 + b22);
# p5:=s1*s5;
p5 := (a21 + a22) * (-b11 + b12);
# p6:=s4*b22;
p6 := (a11 + a12 - a21 - a22)*b22;
# p7:=a22*s8;
p7 := a22 * (b11 - b12 - b21 + b22);
# t1:=p1+p2;
# t2:=t1+p4;
# d11:=p2+p3;
c11 := p2 + p3;
# d12:=t1+p5+p6;
c12 := p1 + p2 + p5 + p6;
# d21:=t2-p7;
c21 := p1 + p2 + p4 - p7;
# d22:=t2+p5;
c22 := p1 + p2 + p4 + p5;
# D:={{c11,c12},{c21,c22}};
# Simplify(A*B - D);