行列乗算アルゴリズムの基本とC++実装例をわかりやすく解説

この記事では、2つの行列の掛け算（行列乗算）を行うアルゴリズムについて解説します。行列の乗算は、任意の組み合わせに対して常に定義できるわけではなく、次元に関する条件を満たす必要がある点に注意しましょう。

いま、2つの行列を A と B とし、それぞれのサイズを A（m × n）、B（p × q）とします。このとき、積の行列 C を求められるのは n = p の場合、すなわち「1つ目の行列の列数」と「2つ目の行列の行数」が一致するときだけです。この条件を満たしていれば、結果となる行列 C のサイズは（m × q）になります。

アルゴリズム

行列乗算は、3重のループを用いて以下のように記述できます。

matrixMultiply(A, B):
A のサイズを (m x n)、B のサイズを (p x q) とする
Begin
    if n が p と等しくないなら、終了
    そうでなければ、(m x q) の行列 C を定義
    for i in range 0 to m-1, do
        for j in range 0 to q-1, do
            for k in range 0 to n-1, do
                C[i, j] = C[i, j] + (A[i, k] * B[k, j])
            done
        done
    done
End

手順のポイント

• 次元チェック： 最初に n ≠ p かどうかを確認します。一致しない場合は乗算が定義できないため、そこで処理を終了します。
• 初期化： 結果を格納する行列 C（m × q）を用意し、全要素を 0 で初期化します。
• 累積加算： i・j・k の3重ループの中で「C[i][j] += A[i][k] × B[k][j]」を計算し続けることで、各行と各列の内積の総和が求まります。

なお、このアルゴリズムは3重ループ構造のため、計算量は O(n³) となります。行列のサイズが大きくなるほど計算コストが増大するため、大規模なデータを扱う場合はブロック化などの最適化手法が検討されることもあります。

C++による実装例

次に、実際にC++で書いたサンプルプログラムを見てみましょう。ここでは3×3の行列2つを掛け合わせています。

#include<iostream>
using namespace std;
int main() {
    int product[10][10], r1=3, c1=3, r2=3, c2=3, i, j, k;
    int a[3][3] = {
        {2, 4, 1},
        {2, 3, 9},
        {3, 1, 8}
    };
    int b[3][3] = {
        {1, 2, 3},
        {3, 6, 1},
        {2, 4, 7}
    };
    if (c1 != r2) {
        cout<<"1つ目の行列の列数は、2つ目の行列の行数と一致している必要があります";
    } else {
        cout<<"1つ目の行列:"<<endl;
        for(i=0; i<r1; ++i) {
            for(j=0; j<c1; ++j)
                cout<<a[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
        cout<<"2つ目の行列:"<<endl;
        for(i=0; i<r2; ++i) {
            for(j=0; j<c2; ++j)
                cout<<b[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
        for(i=0; i<r1; ++i)
            for(j=0; j<c2; ++j) {
                product[i][j] = 0;
            }
        for(i=0; i<r1; ++i)
            for(j=0; j<c2; ++j)
                for(k=0; k<c1; ++k) {
                    product[i][j]+=a[i][k]*b[k][j];
                }
        cout<<"2つの行列の積:"<<endl;
        for(i=0; i<r1; ++i) {
            for(j=0; j<c2; ++j)
                cout<<product[i][j]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

実行結果

1つ目の行列:
2 4 1
2 3 9
3 1 8

2つ目の行列:
1 2 3
3 6 1
2 4 7

2つの行列の積:
16 32 17
29 58 72
22 44 66