use*_*352 0 algorithm recursion matrix matrix-multiplication
Divide&Conquer Matrix Multiplication是否会执行与经典矩阵乘法相同的加法/减法量？
我知道他们专门针对乘法,因为它们都具有相同的O(n ^ 3)复杂度......
但是当我尝试在我正在制作的程序中计算它们时,添加/减少会出现不同的数字,我不确定这是否正确.
如果有人知道,请告诉我,谢谢.
nin*_*cko 10
我们假设平方矩阵.
如果计算经典矩阵乘法中的加法数(没有减法),则会得到N ^ 3个加法.有N ^ 2个元素,每个元素是由N-1个加法组成的行和列的点积,所以几乎完全是N ^ 3个加法.
要计算分而治之矩阵乘法中的加法数,让我们看看它是如何工作的:
将NxN矩阵分解为四个(N/2)x(N/2)矩阵,然后将其视为2x2矩阵并递归地执行块乘法.例如,将两个8x8矩阵相乘:
??A A A A??B B B B?? ??a a a a??b b b b??
??A A A A??B B B B?? ??a a a a??b b b b??
??A A A A??B B B B?? ??a a a a??b b b b??
??A A A A??B B B B?? ??a a a a??b b b b??
??C C C C??D D D D??*??c c c c??d d d d??
??C C C C??D D D D?? ??c c c c??d d d d??
??C C C C??D D D D?? ??c c c c??d d d d??
??C C C C??D D D D?? ??c c c c??d d d d??
新矩阵将是:
?? ?? ??
?? Aa+Bc ?? Ab+Bd ??
?? ?? ??
?? ?? ??
?? ?? ??
?? Ca+Dc ?? Cb+Dd ??
?? ?? ??
?? ?? ??
(where for example Aa is a 4x4 matrix multiplication)
[N/2xN/2]*[N/2xN/2]的每次乘法是大小为N/2的子问题.我们必须做其中的8个子问题.这让我们从上面再次发生:
additions[N] = 8*additions[N/2] + N^2
也就是说,如果我们支付N ^ 2个加法的价格,我们就可以将大小为N的问题分解为8个大小为N/2的子问题.我们可以使用Master Theorem(或更一般的Akra-Bazzi定理)或通过检查来解决:
additions[N] = 8*(8*(8*(8*(..1..) +(N/8)^2) +(N/4)^2) +(N/2)^2) +N^2
使用主定理,additions[N] = O(N^(log_2(8))) = O(N^3)
为什么我们会这样做,因为它是相同的增长顺序？我们不会.事实证明,为了获得更好的渐近复杂度,你不想这样做,你想要使用一种称为Strassen方法的代数技巧.请参见第4页上的http://www.cs.berkeley.edu/~jordan/courses/170-fall05/notes/dc.pdf.我们新的递归关系来自计算该页面上显示的乘法和加法的数量.形成NxN矩阵需要添加18个[N/2xN/2]矩阵.
additions[N] = 7*additions[N/2] + 18*(N/2)^2
= 7*additions[N/2] + (18/4)*(N/2)^2
正如我们所看到的,我们必须减少一个子问题,但代价是在组合方面做更多的工作.主定理说additions[N] = O(N^(log_2(7))) ~= O(N^2.807).
所以渐近地,会有少数增加,但只是渐近.当我们模拟两个递归关系时,真实的故事被揭示:
#!/usr/bin/python3
n = 1 # NxN matrix
normal = 1
naive = 1
strassen = 1
print('NUMBER OF ADDITIONS')
print(' NxN | normal naive strassen | best')
print('-'*60)
while n < 1000000000:
n *= 2
normal = (n-1)*n**2
naive = 8*naive + n**2
strassen = 7*strassen + (18/4)*n**2
print('{:>10} | {:>8.2e} {:>8.2e} {:>8.2e} | {}'.format(
n,
normal, naive, strassen/normal,
'strassen' if strassen<n**3 else 'normal'
))
结果:
NUMBER OF ADDITIONS
NxN | normal naive strassen | best
------------------------------------------------------------
2 | 4.00e+00 1.20e+01 2.50e+01 | normal
4 | 4.80e+01 1.12e+02 2.47e+02 | normal
8 | 4.48e+02 9.60e+02 2.02e+03 | normal
16 | 3.84e+03 7.94e+03 1.53e+04 | normal
32 | 3.17e+04 6.45e+04 1.12e+05 | normal
64 | 2.58e+05 5.20e+05 7.99e+05 | normal
128 | 2.08e+06 4.18e+06 5.67e+06 | normal
256 | 1.67e+07 3.35e+07 4.00e+07 | normal
512 | 1.34e+08 2.68e+08 2.81e+08 | normal
1024 | 1.07e+09 2.15e+09 1.97e+09 | normal
2048 | 8.59e+09 1.72e+10 1.38e+10 | normal
4096 | 6.87e+10 1.37e+11 9.68e+10 | normal
8192 | 5.50e+11 1.10e+12 6.78e+11 | normal
16384 | 4.40e+12 8.80e+12 4.75e+12 | normal
32768 | 3.52e+13 7.04e+13 3.32e+13 | strassen
65536 | 2.81e+14 5.63e+14 2.33e+14 | strassen
131072 | 2.25e+15 4.50e+15 1.63e+15 | strassen
262144 | 1.80e+16 3.60e+16 1.14e+16 | strassen
524288 | 1.44e+17 2.88e+17 7.98e+16 | strassen
1048576 | 1.15e+18 2.31e+18 5.59e+17 | strassen
2097152 | 9.22e+18 1.84e+19 3.91e+18 | strassen
4194304 | 7.38e+19 1.48e+20 2.74e+19 | strassen
8388608 | 5.90e+20 1.18e+21 1.92e+20 | strassen
16777216 | 4.72e+21 9.44e+21 1.34e+21 | strassen
33554432 | 3.78e+22 7.56e+22 9.39e+21 | strassen
67108864 | 3.02e+23 6.04e+23 6.57e+22 | strassen
134217728 | 2.42e+24 4.84e+24 4.60e+23 | strassen
268435456 | 1.93e+25 3.87e+25 3.22e+24 | strassen
536870912 | 1.55e+26 3.09e+26 2.25e+25 | strassen
1073741824 | 1.24e+27 2.48e+27 1.58e+26 | strassen
我们可以看到,就加法而言,Strassen在加法数方面优于传统的正常矩阵乘法,但只有在矩阵超过大约30000x30000的情况下才会出现.
(另请注意,就增加而言,天真的分而治之的乘法与传统的矩阵乘法渐近地相同.但是,它仍然表现为"差",最初为3倍,但随着矩阵大小的增加,渐近变差当然,这并没有告诉我们涉及乘法的真正复杂性,但如果确实如此,如果我们有一个可以利用不同计算结构的并行算法,我们可能仍然想要使用它.)