余因子展開で逆行列を計算してみる

ARToolKit5で大きめの逆行列を解く必要があったので、余因子展開で計算するクラスを作りました。
このクラスは、逆行列の公式を全て展開後に因数分解して、同一な計算を省略する最適化をしたものです。

2x2～18x18行列用のクラスがあります。

Javaで使用できるのは9x9くらいまでで、それ以上はコードサイズが大きすぎてコンパイルできません。
ほかの処理系（.NET）などなら動くと思います。

f:id:nyatla:20160312140620p:plain

行列のサイズと計算量のグラフです。行列サイズが１大きくなると、概ね2.3倍計算量が増えていました。
変数のストア回数はそのままワークエリアのサイズになります。変数を再利用すれば、ワークエリアは半分程度にできると思います。

実際に計算量とメモリ消費量を測定してみると、使い物になるのは5x5行列が限界なことが分かりました。
それ以上のサイズで逆行列を余因子展開で求めるのは大変コストがかかるので、別の方法が良いです。

祖行列で計算を省略した場合は、行列の密度に比例して計算量が減少しました。
例えば、密度が50%の8x8行列の場合、計算量は7x7行列とほぼ同じになります。

大きな行列の余因子展開は全く意味のないことなので、くれぐれも自作しないことをお勧めします。