天天看點

strassen算法

strassen算法:

     第一步:分解輸入矩陣A、B和輸出矩陣C為n/2xn/2的子矩陣。A--->A11、A12、A21、A22, B---->B11、B12、B21、B22,  C---->C11,C12,C21,C22

     第二步:建立十個矩陣

                                           S1=B12 - B22

                                           S2=A11 + A12

                                           S3 = A21 + A22

                                           S4 = B21 - B11

                                           S5 = A11 + A22

                                           S6 = B11 + B22

                                           S7 = A12 + A22

                                           S8 = B21 + B22

                                           S9 = A11 - A21

                                           S10 = B11 + B22

      第三步:遞歸七個矩陣積

                                           P1 = A11 * S1

                                           P2 = B22 * S2

                                           P3 = B11 * S3

                                           P4 = A22 * S4

                                           P5 = S5 * S6

                                           P6 = S7 * S8

                                           P7 = S9 * S10

      第四步:計算出結果矩陣的子矩陣

                                            C11 = P5 + P4 - P2 + P6

                                            C12 = P1 + P2

                                            C21 = P3 + P4

                                            C22 = P5 + P1 - P3 - P7

Strassn算法運作時間T(n)的遞歸式:

                                                            T(n) = 7 * T(n / 2) + theta(n^2)      當 n > 1

                                                             T(n) = theta(1)               當n = 1

由主定理,f(n) = theta(n^2) = O(n^log2(7)),是以T(n) = theta(n^log2(7)),約等于theta(n^log2(2.807))。對于一般的矩陣乘法來說,時間複雜度的最小下界是theta(n^2),因為有結果矩陣由n^2個元素。

參見《算法導論》