行列計算 — 知識ノート

数値線形代数。科学計算の中核。

BLAS と LAPACK#

Level 3 が最も効率が良い。

\frac{演算回数}{メモリアクセス} = \frac{O (n^{3})}{O (n^{2})} = O (n)

データ 1 個あたりの計算量が多いほど、メモリ帯域の制約から逃れられる。そのためアルゴリズムを行列積の形に持ち込むのが定石。

同じ $O (n^{3})$ でも、素朴な三重ループと OpenBLAS では100 倍以上違う。

自分で行列積を書かない。 既存の実装を使う。

python

x = np.linalg.inv(A) @ b     # 遅く、精度も悪い
x = np.linalg.solve(A, b)    # こちら

逆行列を明示的に求めるのは 計算量が多く、誤差も増える。連立方程式として解くのが常に正しい。

κ (A) = ‖ A ‖ ‖ A^{- 1} ‖

条件数が大きい（悪条件）と、入力のわずかな誤差が解を大きく狂わせる。

\frac{‖ δ x ‖}{‖ x ‖} \leq κ (A) \frac{‖ δ b ‖}{‖ b ‖}

$κ \approx 10^{16}$ なら倍精度の有効数字が全部失われる。 解が出たことと、その解が正しいことは別。

Gene H. Golub, Charles F. Van Loan. Matrix Computations, 4th ed. Johns Hopkins University Press, 2013.
Lloyd N. Trefethen, David Bau III. Numerical Linear Algebra. SIAM, 1997. https://doi.org/10.1137/1.9780898719574
Kazushige Goto, Robert A. van de Geijn. Anatomy of high-performance matrix multiplication. ACM TOMS 34(3), 2008. https://doi.org/10.1145/1356052.1356053