设矩阵 (A,B,C) 均为 (n) 阶方阵，(n=2^k,kin Z)
给定 (A_{n imes n}=left(a_{ij} ight),B_{n imes n}=left(b_{ij} ight)) ，求解 (C_{n imes n}=A_{n imes n}cdot B_{n imes n})
【矩阵分块的引入】
将矩阵 (A,B,C) 进行分块，使得分块后各个子矩阵均为 ({nover 2}) 阶方阵，记 (A=left( egin{matrix} A_{11}&A_{12} \ A_{21}&A_{22} end{matrix} ight),B=left( egin{matrix} B_{11}&B_{12} \ B_{21}&B_{22} end{matrix} ight),C=left( egin{matrix} C_{11}&C_{12} \ C_{21}&C_{22} end{matrix} ight))
则由矩阵分块乘法可得：
(C_{11}=A_{11}B_{11}+A_{12}B_{21})
(C_{12}=A_{11}B_{12}+A_{12}B_{22})
(C_{21}=A_{21}B_{11}+A_{22}B_{21})
(C_{22}=A_{21}B_{12}+A_{22}B_{22})
由观察可得，分块后需要对 ({nover 2}) 阶方阵进行 (8) 次矩阵乘法与 (4) 次矩阵加法
【矩阵分块递归的复杂度】
设分块后需要将矩阵进行 (a) 次矩阵乘法与 (b) 次矩阵加法，以及 (c) 次的某 (O(n)) 操作， (d) 次的某 (O(1)) 操作
不难列出复杂度递推式：(T(n)=aT({nover 2})+bn^2+cn+d)
代入 (n=2^k) 得 (T(k)=aT(k-1)+bcdot 4^k+ccdot 2^k+d)
通过解递推方程可得： (T(k)=a^k+{4bover 4-a}cdot 4^k+{2cover 2-a}cdot 2^k+{dover 1-a},a>4)
代回 (2^k=n) 得 (T(n)=n^{log_2 a}+{4bover 4-a}n^2+{2cover 2-a}n+{dover 1-a}=n^{log_2 a}+{4bover 4-a}n^2+o(n^2))
因此，代入朴素矩阵分块的数值 (a=8,b=4) 得 (T(n)=n^{log_2 8}+{4 imes 4over 4-8}n^2+o(n^2)=n^3-n^2+o(n^2)=O(n^3))
在渐进意义下，与普通矩阵乘法无复杂度差别
【Strassen算法】
记录以下中间矩阵：
(S_1=B_{12}-B_{22})
(S_2=A_{11}+A_{12})
(S_3=A_{21}+A_{22})
(S_4=B_{21}-B_{11})
(S_5=A_{11}+A_{22})
(S_6=B_{11}+B_{22})
(S_7=A_{12}-A_{22})
(S_8=B_{21}+B_{22})
(S_9=A_{11}-A_{21})
(S_{10}=B_{11}+B_{12})
然后再记录：
(P_1=A_{11}cdot S_1)
(P_2=S_2cdot B_{22})
(P_3=S_3cdot B_{11})
(P_4=A_{22}cdot S_4)
(P_5=S_5cdot S_6)
(P_6=S_7cdot S_8)
(P_7=S_9cdot S_{10})
最后即可得到：
(C_{11}=P_5+P_4-P_2+P_6)
(C_{12}=P_1+P_2)
(C_{21}=P_3+P_4)
(C_{22}=P_5+P_1-P_3-P_7)
由于用到了 (7) 次矩阵乘法与 (18) 次矩阵加法/减法，故代入 (a=7,b=18) 得到 (T(n)=n^{log_2 7}+{4cdot 18over 4-7}n^2+o(n^2)=n^{log_2 7}-24n^2+o(n^2)=O(n^{log_2 7})approx O(n^{2.807}))
【看法】
由于复杂度满足 (T(n)=n^{log_2 a}+{4bover 4-a}n^2+o(n^2)) ，故如果能通过矩阵间的线性组合，进一步减小矩阵乘法的次数，则渐进复杂度还将更优