Design-and-analysis-of-algorithms-strassens-matrix-multiplication

DAA-Strassenの行列乗算

この章では、まず行列乗算の一般的な方法について説明し、後でStrassenの行列乗算アルゴリズムについて説明します。

問題文

2つの行列 X と Y を考えてみましょう。 X と Y を乗算して、結果のマトリックス Z を計算します。

ナイーブ法

最初に、単純な方法とその複雑さについて説明します。 ここでは、 _ Z = X×Y_ を計算しています。 ナイーブ法を使用すると、これらの行列の順序が p×q と q×r の場合、2つの行列（ X と Y ）を乗算できます。 アルゴリズムは次のとおりです。

Algorithm: Matrix-Multiplication (X, Y, Z)
for i = 1 to p do
   for j = 1 to r do
      Z[i,j] := 0
      for k = 1 to q do
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

複雑

ここでは、整数演算に O（1） 時間かかると想定しています。 このアルゴリズムには3つの for ループがあり、一方はもう一方にネストされています。 したがって、アルゴリズムの実行には O（n ^ 3 ^） 時間かかります。

Strassenの行列乗算アルゴリズム

このコンテキストでは、Strassenの行列乗算アルゴリズムを使用して、時間消費を少し改善できます。

Strassenの行列乗算は、正方行列（ n は* 2のべき乗*）でのみ実行できます。 両方の行列の次数は n×n です。

以下に示すように、 X 、 Y 、および Z を4つの（n/2）×（n/2）行列に分割します−

$ Z = \ begin \ {bmatrix} I＆J \\ K＆L \ end \ {bmatrix} $ $ X = \ begin \ {bmatrix} A＆B \\ C＆D \ end \ {bmatrix} $および$ Y = \ begin \ {bmatrix} E＆F \\ G＆H \ end \ {bmatrix} $

Strassenのアルゴリズムを使用して、以下を計算します-

M _ \ {1} \：\ colon =（A + C）\ times（E + F）

M _ \ {2} \：\ colon =（B + D）\ times（G + H）

M _ \ {3} \：\ colon =（A-D）\ times（E + H）

M _ \ {4} \：\ colon = A \ times（F-H）

M _ \ {5} \：\ colon =（C + D）\ times（E）

M _ \ {6} \：\ colon =（A + B）\ times（H）

M _ \ {7} \：\ colon = D \ times（G-E）

その後、

I \：\ colon = M _ \ {2} + M _ \ {3}-M _ \ {6}-M _ \ {7}

J \：\ colon = M _ \ {4} + M _ \ {6}

K \：\ colon = M _ \ {5} + M _ \ {7}

L \：\ colon = M _ \ {1}-M _ \ {3}-M _ \ {4}-M _ \ {5}

分析

$ T（n）= \ begin \ {cases} c＆if \：n = 1 \\ 7 \：x \：T（\ frac \ {n} \ {2}）+ d \：x \：n ^ 2およびそれ以外の場合\ end \ {cases} $ここで、_c_および_d_は定数です

この再帰関係を使用して、$ T（n）= O（n ^ \ {log7}）$を取得します

したがって、Strassenの行列乗算アルゴリズムの複雑さは$ O（n ^ \ {log7}）$です。