分而治之矩阵乘法与经典矩阵乘法执行相同数量的加法/减法吗？

-1

是否划分&征服矩阵乘法执行与经典矩阵乘法相同数量的加法/减法？分而治之矩阵乘法与经典矩阵乘法执行相同数量的加法/减法吗？

我知道他们为乘法做专，因为它们都共享同为O（n^3）复杂...

但是当我尝试在节目指望他们我正在做的添加/减法来到不同的数字，我不确定这是否正确。

如果有人知道肯定请让我知道，谢谢。

2012-02-20 user1189352

一个互联网搜索会回答这个问题.... – 2012-02-20 03:17:52

这似乎非常相似[你的问题从两个小时前]（http://stackoverflow.com/questions/9355022/can-someone-tell-我最复杂性的最加减换的鸿沟）。 – DSM 2012-02-20 03:22:51

我已经尝试过..我想我的谷歌技能吸吮 – user1189352 2012-02-20 03:22:57

我们假设平方矩阵。

如果您计算经典矩阵乘法中的加法次数（没有减法），则会得到N^3个加法。有N^2个元素，每个元素是由N-1个加法组成的行和列的点积，所以几乎正好是N^3个加法。

要计算的分而治之矩阵乘法加法的次数，让我们来看看它是如何工作的：

拆分多达NxN矩阵为四个（N/2）×（N/2）的矩阵，然后将其视为2x2矩阵并递归执行块乘法。例如乘以两个8×8矩阵：

┌┌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/2×N个/ 2] * [N/2×N个/ 2]是一个子问题大小N/2。我们必须做8个这样的子问题。这给了我们从上面的复发：

additions[N] = 8*additions[N/2] + N^2

也就是说，如果我们付出N^2所增加的价格，我们被允许打破大小为N的问题分解成大小为N/2 8子问题。我们可以使用主定理（或更一般的Akra-Bazzi定理）解决，或者通过检查：

additions[N] = 8*(8*(8*(8*(..1..) +(N/8)^2) +(N/4)^2) +(N/2)^2) +N^2

使用Master Theorem，additions[N] = O(N^(log_2(8))) = O(N^3)

为什么我们这样做，因为它的增长同阶？我们不会。事实证明，为了获得更好的渐近复杂性，你不想这样做，你想使用称为Strassen方法的代数技巧。请参阅第4页上的http://www.cs.berkeley.edu/~jordan/courses/170-fall05/notes/dc.pdf。我们新的递归关系来自对该页面上显示的乘法和加法数的计数。有18个增加的[N/2xN/2]矩阵需要形成一个NxN矩阵。

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

我们可以看到，相对于只添加，施特拉森优于传统正常的矩阵乘法对于到添加数量，但只有您的矩阵超过大约30000x30000的大小。（另外注意，就加法而言，天真的分而治之乘法与传统的矩阵乘法相比，渐进地实现了相同的效果，然而它仍然以最初为3的因子执行“更差”，但是作为矩阵大小当然这并没有告诉我们涉及乘法的真正复杂性，但如果它真的存在，如果我们有一个可以利用不同的并行算法的并行算法，我们可能仍然希望使用它计算结构）。

来源

2012-02-20 05:27:59 ninjagecko

谢谢，这非常有帮助 – user1189352 2012-02-21 04:19:10

-1

如果在谈论简单的分而治之矩阵乘法算法（而不是Strassens方法），那么与正常矩阵乘法相比，操作次数是相同。

This链路提到：

在这种情况下，分而治之方法导致完全相同数目的操作作为矩阵乘法的“正常”的方法。上面的再现来自这样一个事实，即当将普通方法应用于2乘2矩阵时，需要8次乘法和4次加法。

来源

2012-02-20 04:03:16

分而治之矩阵乘法与经典矩阵乘法执行相同数量的加法/减法吗？

回答

相关问题