Matrix multiplications

Работа над этим материалом еще не окончена.

A, B, C are n*n matrices.

A x B = C = matrix:

$A_{11}B_{11} + A_{12}B_{21}$	$A_{11}B_{12} + A_{12}B_{22}$
$A_{21}B_{11} + A_{22}B_{21}$	$A_{21}B_{21} + A_{21}B_{22}$

Define T(n) as time to multiply two n*n matrices.

T(1) = 1

T(n) = 8T(n/2) + O(n^2) = 8T(n/2) + cn^2 for some constant c>0.

Assume n=2^k for some positive integer k.

Then, T(n) = cn^2 + 8T(n/2)

= cn^2 + 8(8T(n/2^2) + c (n/2)^2)

= сn^2(1+8/2^2)+8^2T(n/2^2)

= cn^2(1+8^2)+8^2*(8T(n/2^4)+c(n/2)^4)

= cn^2(1+8/2^2+8/2^4) + ...

= cn^2(1+8/2^2+8^2/2^4+ … 8^(k-1)/(2^(k-1)^2)+8^k *T (n/2^k)

where 8^k=n^3

= cn^2(2^(k)-1)/(2-1) + 8^k*T(1)

$A_{11}B_{11} + A_{12}B_{21}$	$A_{11}B_{12} + A_{12}B_{22}$
$A_{21}B_{11} + A_{22}B_{21}$	$A_{21}B_{21} + A_{21}B_{22}$