节约计算:先算x= (a+b)(c-d) = (ac-bd)+bc-ad; 左侧只有1次乘法(加法耗计算比乘法几乎忽略不计,所以比算力一般是mfps浮点乘法算的),再算y = ad ,z = bc 需要两次计算; 最后 (a+jb)(c+jd) = (x+y-z) +j(-y+z) 得到最终值;
非常简单,节约了一次计算,每次复数乘都能介于,效果显著,原理粗暴,就是简单代数。
二维矩阵,最初strassen算法,8次乘节约1次,提效12.5%
上述原理可以由数学家进一步拓展到2D,矩阵乘法,通过7次代数乘,替代一次8次乘法的矩阵乘法。
f
(
n
)
=
7
f
(
n
/
2
)
+
θ
(
n
)
f(n) =7f(n/2)+\theta (n)
f(n)=7f(n/2)+θ(n) ,则由主分析法知道他削减了nxn维度两个矩阵相乘,从
θ
(
n
3
)
\theta(n^3)
θ(n3)到
θ
(
n
l
o
g
2
7
)
=
θ
(
n
2.8
)
\theta(n^{log_2^7})=\theta(n^{2.8})
θ(nlog27)=θ(n2.8)