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

Question

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

我知道它们专门用于乘法运算，因为它们具有相同的 O(n^3) 复杂度...

但是当我尝试在我正在制作的程序中对它们进行计数时，加法/减法得到了不同的数字，我不确定这是否正确。

如果有人知道请告诉我，谢谢。

Answer 1

让我们假设方阵。

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

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

将 NxN 矩阵拆分为四个 (N/2)x(N/2) 矩阵，然后将其视为 2x2 矩阵并递归执行 block 乘法。 例如将两个 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 的问题分解为大小为 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。我们的新递归关系来自于计算该页上显示的乘法和加法的次数。需要[N/2xN/2]个矩阵相加18次才能构成一个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

正如我们所见，仅在加法方面，Strassen 优于传统的普通矩阵乘法在加法次数方面，但前提是您的矩阵超过大约 30000x30000 的大小。

(另请注意，就加法而言，朴素的分而治之乘法与传统矩阵乘法渐进地执行相同的操作。但是，它最初的性能仍然“更差”3 倍，但随着矩阵大小的增加, 渐进地差了 2 倍。当然，这并没有告诉我们涉及乘法的真正复杂性，但如果确实如此，如果我们有一个可以利用不同计算的并行算法，我们可能仍然想使用它结构。)