设矩阵 \(A,B,C\) 均为 \(n\) 阶方阵，\(n=2^k,k\in Z\)
给定 \(A_{n\times n}=\left(a_{ij}\right),B_{n\times n}=\left(b_{ij}\right)\) ，求解 \(C_{n\times n}=A_{n\times n}\cdot B_{n\times n}\)
【矩阵分块的引入】将矩阵 \(A,B,C\) 进行分块，使得分块后各个子矩阵均为 \({n\over 2}\) 阶方阵，记 \(A=\left( \begin{matrix} A_{11}&A_{12} \\ A_{21}&A_{22} \end{matrix} \right),B=\left( \begin{matrix} B_{11}&B_{12} \\ B_{21}&B_{22} \end{matrix} \right),C=\left( \begin{matrix} C_{11}&C_{12} \\ C_{21}&C_{22} \end{matrix} \right)\)
则由矩阵分块乘法可得：
\(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}\)
由观察可得，分块后需要对 \({n\over 2}\) 阶方阵进行 \(8\) 次矩阵乘法与 \(4\) 次矩阵加法
【矩阵分块递归的复杂度】设分块后需要将矩阵进行 \(a\) 次矩阵乘法与 \(b\) 次矩阵加法，以及 \(c\) 次的某 \(O(n)\) 操作， \(d\) 次的某 \(O(1)\) 操作
不难列出复杂度递推式：\(T(n)=aT({n\over 2})+bn^2+cn+d\)
代入 \(n=2^k\) 得 \(T(k)=aT(k-1)+b\cdot 4^k+c\cdot 2^k+d\)
通过解递推方程可得： \(T(k)=a^k+{4b\over 4-a}\cdot 4^k+{2c\over 2-a}\cdot 2^k+{d\over 1-a},a>4\)
代回 \(2^k=n\) 得 \(T(n)=n^{\log_2 a}+{4b\over 4-a}n^2+{2c\over 2-a}n+{d\over 1-a}=n^{\log_2 a}+{4b\over 4-a}n^2+o(n^2)\)
因此，代入朴素矩阵分块的数值 \(a=8,b=4\) 得 \(T(n)=n^{\log_2 8}+{4\times 4\over 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_2\cdot B_{22}\)
\(P_3=S_3\cdot B_{11}\)
\(P_4=A_{22}\cdot S_4\)
\(P_5=S_5\cdot S_6\)
\(P_6=S_7\cdot S_8\)
\(P_7=S_9\cdot 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}+{4\cdot 18\over 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}+{4b\over 4-a}n^2+o(n^2)\) ，故如果能通过矩阵间的线性组合，进一步减小矩阵乘法的次数，则渐进复杂度还将更优