分而治之矩陣乘法與經典矩陣乘法執行相同數量的加法/減法嗎？

-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

分而治之矩陣乘法與經典矩陣乘法執行相同數量的加法/減法嗎？

回答

相關問題