matlab - MATLAB での行列乗算時間の計算量

Question

MATLABが行列の乗算に使用するアルゴリズムと、その時間の複雑さを知っている人はいますか?

Answer 1

完全を期すために、このスレッドで述べたように、Matlab はBLAS (Basic Linear Algebra Subprograms)のDGEMM(Double GEneral Matrix Multiplication) ルーチンを使用します。

BLAS の実装は 1 つではなく、特定のプロセッサ アーキテクチャに合わせて調整されていることに注意してください。したがって、どのバージョンの BLAS が使用されているかを調べなければ、マシンでどのアルゴリズムが使用されているかを完全に特定することはできません。

BLAS の仕様は、各サブルーチンの入力と出力を指定し、各サブルーチンの出力の許容誤差範囲を提供します。実装は、仕様に従っている限り、好きなアルゴリズムを自由に使用できます。

BLAS の参照実装では、 2 つのn x n行列を乗算するために時間計算量 O( n ^3) を持つブロック行列乗算アルゴリズムが使用されます。BLAS のほとんどの実装は、多かれ少なかれリファレンス実装に従うと想定するのが妥当だと思います。DGEMM

単純な行列乗算アルゴリズムを使用しないことに注意してください

for i = 1:N
    for j = 1:N
        for k = 1:N
            c(i,j) = c(i,j) + a(i,k) * b(k,j);
        end
    end
end

これは、通常、行列全体がローカル メモリに収まらないためです。データが常にローカル メモリにシフトされたり、ローカル メモリからシフトされたりすると、アルゴリズムの速度が低下します。ブロック マトリックス アルゴリズムは、操作を小さなブロックに分割します。各ブロックは、ローカル メモリに収まるほど小さくなり、メモリへのシフトとメモリからのシフトの回数が減ります。

漸近的に高速な行列乗算アルゴリズムが存在します。たとえば、 O( n ^3)よりわずかに高速なStrassen アルゴリズムやCoppersmith-Winograd アルゴリズムがあります。ただし、それらは一般にキャッシュを認識せず、局所性を無視します。つまり、データをメモリ内で絶えずシャントする必要があるため、最新のアーキテクチャのほとんどでは、アルゴリズム全体が実際には最適化されたブロック行列乗算アルゴリズムよりも遅くなります。

ウィキペディアによると、Strassen アルゴリズムは、単一コア CPU で数千を超える行列サイズのスピードアップを提供する可能性がありますが、スピードアップは約 10% 程度である可能性が高く、BLAS の開発者はおそらく、このまれなケースでは価値があるとは考えていません。ケース（そうは言っても、 1996年のこの論文では、約200を超えるnに対してDGEMM約10％の速度向上が主張されていますが、それがどれほど時代遅れであるかはわかりません）。一方、Coppersmith-Winograd アルゴリズムは、「最新のハードウェアでは処理できないほど大きな行列に対してのみ利点を提供します」。

その答えは、Matlab が単純だが効率的でキャッシュを認識するアルゴリズムを使用して、非常に高速な行列乗算を取得することです。

---

単純なアルゴリズムと比較して、ブロック行列乗算アルゴリズムの局所性を示すいくつかのビデオを作成して、この回答を更新しました。

次の各ビデオでは、2 つの 8x8 行列AとBの乗算を視覚化して、積C = A x Bを作成しています。黄色の強調表示は、行列A、B、およびCのそれぞれのどの要素がアルゴリズムの各ステップで処理されているかを示します。ブロック行列の乗算が一度に行列の小さなブロックに対してのみ機能し、それらの各ブロックを複数回再利用する方法を確認できます。これにより、データがローカル メモリにシフトインおよびシフトアウトされる回数が最小限に抑えられます。 .

• 単純行列乗算
• ブロック行列の乗算、ブロック サイズ = 2
• ブロック行列の乗算、ブロック サイズ = 4