MATLABの行列乗算時間の複雑さ

Question

MATLABが行列の乗算に使用するアルゴリズムとその時間の複雑さは誰にも分かりますか？

Answer 1

this threadに記載されているように、Matlabは（Basic Linear Algebra Subprograms）のDGEMM（Double GEneral Matrix Multiplication）ルーチンを使用しています。

BLASの実装は1つではありません。特定のプロセッサアーキテクチャ用に調整されています。したがって、どのバージョンのBLASが使用中であるかを見出すことなく、あなたのマシンでどのアルゴリズムが使用されているかを絶対に確認することはできません。

BLASの仕様は、各サブルーチンの入力と出力を指定し、各サブルーチンの出力に許容可能なエラー境界を提供します。実装は、仕様に準拠している限り、好きなアルゴリズムを自由に使用できます。

BLASのリファレンス実装は、二つN X N行列を乗算する時間複雑性O（N^3）を有するDGEMMでblock matrix multiplication algorithmを使用します。私は、BLASのほとんどの実装がリファレンス実装に多かれ少なかれ続くと仮定することは合理的だと思います。それは一般的に、全体の行列はlocal memoryに収まらない、これは単純な行列の乗算アルゴリズム

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 algorithmまたはCoppersmith-Winograd algorithmは、例えば、漸近的に高速行列乗算アルゴリズムが存在します。しかし、一般的にはキャッシュを認識せず、局所性を無視します。つまり、データがメモリ内で絶えずシャントされる必要があるため、現代のアーキテクチャでは、アルゴリズム全体が最適化ブロック行列乗算アルゴリズムよりも実際には遅くなります。

ウィキペディアは、Strassenアルゴリズムは、数千を超える行列サイズに対して単一コアCPUのスピードアップを提供する可能性があると指摘していますが、スピードアップは約10％程度になる可能性があり、BLASの開発者はおそらく考慮しませんこの希少なケースでは価値があると言います（1996年のthis paperは、DGEMMのnの約10％のスピード増加を約束しています。一方、Coppersmith-Winogradアルゴリズムは、「現代のハードウェアでは処理できないほど大きな行列に対してのみ利点があります」と述べています。

これは、Matlabが高速で高速な行列乗算を得るために、ナイーブで効率的なキャッシュ認識アルゴリズムを使用していることです。

---

この回答は、ナイーブなアルゴリズムと比較して、ブロック行列乗算アルゴリズムのローカリティを示すビデオを作成することで更新されました。次の動画のそれぞれにおいて

は、我々は製品C = X Bを作成するために、2つの8×8行列とBの乗算を視覚化しています。黄色の強調表示は、アルゴリズムの各ステップでどの行列のどの要素が処理されているかを示す。A,BおよびCブロック行列の乗算は、行列の小さなブロックで一度にどのように機能するかを確認し、それらのブロックを複数回再利用することで、データをローカルメモリに出し入れする回数を最小限に抑えることができます。

• Simple matrix multiplication
• Block matrix multiplication, block size = 2
• Block matrix multiplication, block size = 4