行列の積の処理を高速化したい

質問

3Dのプログラムで行列を扱ってます。
行列の掛け算を行おうとすると

for(i= 0;i<4;i++){
　for(i= 0;i<4;i++){
　　for(i= 0;i<4;i++){
　　　詳細は省きます。。。
　　}
　}
}

のように、3重のfor文の中で掛け合わせていたと思います。
この部分、むかーしどこかのサイトで、
無駄な部分を処理せずに（例えば必ず0の要素の個所は、最初から演算させない等）
高速な処理をさせているロジックを見た事があったのですが、
そのようなに、上記の計算よりは、無駄がなく処理の高速化が望める
アルゴリズムを知りたいのです。

で、よく使われる平行移動行列は
| 1 0 0 0 |
| 0 1 0 0 |
| 0 0 1 0 |
| dx dy dz 1 |

で、それを対応させる行列が
| 00 01 02 03 |
| 10 11 12 13 |
| 20 21 22 23 |
| dx dy dz 44 |

という位置関係になっていると思うのですが、

諸事情により、私が扱う行列の配置は、上記の行列の変数を利用すると

| 00 10 20 dx |
| 01 11 21 dy |
| 02 12 22 dz |
|この行は取り扱わない|

という行列になっています。（各要素の位置が反転しています）
さらに、一番下の行は取り扱わないので（数値が0だから最初から扱う必要がない）
4*4ではないのですが

| 00 10 20 dx |　 | 00 10 20 dx |
| 01 11 21 dy | * | 01 11 21 dy |
| 02 12 22 dz | 　 | 02 12 22 dz |

という計算になります。

わかりにくい説明ですが、この行列の計算を高速化させる
アルゴリズムがありましたら、ぜひご教授ください。
よろしくお願いします。

回答No.4

FM-8

#3です．

いい忘れましたが，#3の方法では
直接配列のアドレスがかかれるので，計算が遅くなるケースもあります．

CPUの内部では，インデックスアドレッシングといいまして，forループの添え字のようなものを用いたほうが速く配列にアクセスできる場合もあるからです．

蛇足でした．

回答No.3

FM-8

4*4のマトリックスの積を計算させるのですね．

たぶん大して速くはならないとは思うのですが，
書き下してしまうという手もあります．

つまり，
|a b| |e f| |ae+bg　af+bh |
| | x | | = | |
|c d| |g h| |ce+dg cf+dh |

という具合です．
あらかじめ手で計算して，ソースに埋め込んでしまいます．

あまり姑息なことをやるよりも，昨今は「最適化コンパイラ」にお任せしたほうが，速くなるケースもありますので，ケースバイケースです．つまり，ご質問のforループがかならずしも遅いとは思いません．

少しでも速くしようと思って，いろいろ工夫しても
結果として大して速くならずがっかりすることもよくあります．

回答No.2

cherry_moon

boostというC++のライブラリがあるようです。
http://boost.cppll.jp/HEAD/index.htm

疎な行列向けの関数を使うにはこれをインクルードすればいいみたいです。
#include <boost/numeric/ublas/matrix_sparse.hpp>

参考URL：

http://boost.cppll.jp/HEAD/libs/numeric/ublas/doc/matrix_sparse.htm

回答No.1

sha-girl

アルゴリズムでは無いですが
1.行列積の部分をインラインアセンブラにする。
2.1で更にSSE命令を利用して、浮動小数点の演算を一気に行う。
3.シェーダーを使う(CPUでは無くグラフィックボードに演算させる)
等がベクトル演算を高速化させる手段として有効です。

>むかーしどこかのサイトで、
>無駄な部分を処理せずに（例えば必ず0の要素の個所は、最初から演算させない
昔(コプロセッサが別だった頃)は浮動小数点の計算が遅かったため、そういうアルゴリズムも組めたかもしれませんが
現在のCPU(Pentium4等)のfloatの演算に関していえば、整数の演算とほぼ同じ速度です。
その為0かどうかを毎回チェックするぐらいなら、そのまま演算させた方が高速なのです。
(ちなみにdoubleの演算は遅い為、高速化を望むなら避けた方が良いでしょう。)