概要
- Charles Dodgson （Lewis Carroll）による行列式計算手法「 Dodgson凝縮法」の紹介
- 手計算に適した方法だが、 機械計算 にも有用
- 行列を繰り返し 凝縮 し、行・列を減らしていくアルゴリズム
- ゼロによる割り算回避 のための前処理が必要
- Gaussian eliminationと同等の計算効率、 整数保持 ・並列化が容易
Dodgson凝縮法（Dodgson Condensation）の概要
- Dodgson凝縮法 は、行列式を効率よく計算するための手法
- 行列のサイズを 1つずつ減らしながら 計算を進めるアルゴリズム
- 各要素を、その要素と 南・東・南東 の隣接要素で作る2×2小行列の行列式で置き換える
- 一番下の行と一番右の列は 削除
- 各ステップで 2ステップ前の要素で割り算 を行う必要
アルゴリズム詳細
- 元の行列を A、k回凝縮した行列を A(k) と表記
- A(1) は、2×2小行列の行列式で構成
- A(2) 以降は、各2×2行列式を 2ステップ前の要素で割る
- 割り算の分母の選び方には注意が必要、Dodgson本人の論文でもやや分かりにくい記述
- 計算例：4×4行列での凝縮手順と結果の検証（例：Mathematicaで228を得る）
ゼロによる割り算回避
- アルゴリズム中で ゼロ割り が発生しないようにする必要
- Dodgsonの推奨： 行や列の入れ替え、または 他の行を定数倍して加算 することで内部のゼロを回避
- この前処理は主に ゼロ割り回避 のためだが、他の理由があるかは不明
- 元の行列が 整数成分のみ の場合、途中の計算でも全て整数を保持
効率と他手法との比較
- 初学者は 余因子展開 で行列式計算を学ぶが、これは O(n!) で非効率
- Gaussian elimination （部分ピボット付き消去法）は O(n³) で効率的
- Dodgson凝縮法も O(n³) の計算量
- Gaussian eliminationでもゼロ割り回避のため部分ピボットが必要
- Dodgson凝縮法は手計算しやすく、拡張性も高い
- 途中で整数を保つため、 整数行列 に向いている
- 各2×2行列式は 並列計算 が可能
関連
- 余因子 ・ 行列式 ・ 随伴行列 との関係
- 1の列を持つ行列式 に関する応用
- 応用線形代数 分野での利用