行列の積とそのコスト

写像を合成する

積 $AB$ は、先に $B$、次に $A$ を適用して得られる写像です。$(AB)\mathbf{x}=A(B\mathbf{x})$。積の $(i,j)$ 成分は $A$ の第 $i$ 行と $B$ の第 $j$ 列の内積なので、サイズが合う必要があります。$m\times n$ 行列と $n\times p$ 行列の積は $m\times p$ 行列です。積は結合的で $(AB)C=A(BC)$、和に対して分配的ですが、一般には交換できず $AB\neq BA$ です。2つの操作は順序で結果が変わるからです。

$m\times n$ 行列と $n\times p$ 行列の積 $AB$ には $mnp$ 回の積和（浮動小数点演算で約 $2mnp$ 回）がかかります。$n\times n$ 同士なら $n^3$ で、$n$ を2倍にすると計算量は8倍です。行列とベクトルの積は $n^2$ で済みます。積は結合的なので括弧の付け方で結果は変わりませんが、コストは大きく変わりえます。

• サイズの規則：$(m\times n)(n\times p)=(m\times p)$。内側のサイズが一致する必要があります。
• 非可換：一般に $AB\neq BA$ なので、因子を入れ替えてはいけません。
• コスト：$mnp$ 回の積和。行列×ベクトルは $n^2$、行列×行列は $n^3$。

ラボ：採点される内容

• 積 AB20点
• 積 BA15点
• 積のサイズ10点
• 積和の回数を数える15点
• 2通りの括弧付け20点
• 括弧付けが重要な理由20点