行列計算の速度

質問

行列計算の速度

今、スパース行列計算のプログラミングをしているのですが、Cで作成していて、計算速度について考慮しています。同じような計算をmatlabでさせてみたら、matlabでの行列計算は圧倒的に速かったので、matlabを使う事を考えてます。行列計算を得意とするmatlabなのですが、matlabはCを使っているので、Cでのプログラミングをあきらめるべきなのか考えています。
Cもmatlabも良い点、悪い点はあると思いますが、何か参考になるアドバイスがあればいいなと思って、投稿させてもらいました。お願いします。

回答No.4

Interest

C言語だから遅いというのではなくて、大規模な疎行列にガウスの消去法を使ったから遅いのだと思います。

１００００×１００００の行列を作るために malloc でメモリを確保したそうですが、ザックリ 762MBですか。いまどきのPCだとRAMをGB単位で積むのが当たり前だから気にしないのでしょうか。RAMが少なければスワップが大量に発生しそうな気がします。

Matlabはこのような手法で疎行列の演算を高速化しているようですね。（学生さんの卒論なので、どこまで正しいか保証はできませんが。）
http://dspace.wul.waseda.ac.jp/dspace/bitstream/2065/671/1/1g01p100.pdf

反復法について。
http://sstweb.ee.ous.ac.jp/lecture/ee/NumericalCalculations/ncd20061204.pdf

数値計算法をキーワードにして探せば、大規模な連立一次方程式の解法が見つかるんじゃないでしょうか。
（自分で作るとバグも作っちゃうから、Matlabを使うというのも一つの手だと思います。）

お礼

直接法と反復法の両方試しましたが、やはり直接法が早かったので、それでプログラミングをしてみました。
計算速度を早くするためにいくつか手段があるみたいなので、試してみたいと思います。

回答と、参考資料のリンクありがとうございました。

回答No.3

正親町（@Ohgimachi）

>Cもmatlabも良い点、悪い点はあると思いますが、何か参考になるアドバイスがあればいいなと思って、投稿させてもらいました。

参考になるかどうかは判りませんが、

一般的にＦＰＵを使用した浮動小数点の演算はＣ言語を含むあらゆる高級言語より、アセンブラの方が圧倒的に高速実行が可能です。それは以下の理由によります。
・並列処理の記述が高級言語では不可能
・関数の引数のレジスタ渡しができない
・FPUの特殊機能が高級言語では記述不可能

Intelのx86のプロセッサで説明しますと

(1)並列処理の問題
高級言語で実現不可能なのは以下の並列化処理。
・FPUはパイプラインで動作しており、そのパイプラインに空白を作らないようにプログラミングをする。
・FPUとALUは独立して動作可能（バスは共通）なのでFPUの実行中にALUを使って演算を並列化させる。
FPUとALUを同時に動作させる考え方は昔から存在していたのですが、内蔵キャッシュがなくて外部バスにFPUがブル下がっていた頃はあまり効果がなかったのです。今はキャッシュにデータが入っていれば１クロックでアクセスできますから効果が大きいのです。

(2)関数の引数の問題
C言語では関数に値を渡す場合にスタックを利用するのが一般的です。しかし浮動小数点の演算ではFPUのレジスタを使用するため、以下の問題があります。
・関数の呼び出し側ではFPUのレジスタからデータを取り出し、スタックにプッシュする。
・関数を実行する側ではスタックから値を取り出し、FPUにロードする。
という非常に無駄な作業を繰り返すことになります。引数が多い場合にはスタックを使用するしかありませんが４個程度なら「FPUのレジスタ渡し」が圧倒的に高速です。この技法は３０年前から存在していました。

(3)FPUの特殊機能
IntelのプロセッサーではMMXやSSEを指します。SSEを使用する場合にはC言語では記述の方法がないのでアセンブラでプログラミングをします。

具体的には、IntelのHPから『Intel Architecture Software Developer's Manual』を参照してみてください。

アセンブラで効率がよく実行速度が速いプログラムを書くのは職人芸です(^^)ノ
ちなみに私はmatlabではなくてscilabを使用しています。ソースコードの提供も含めて無料なので＾＾

お礼

scilabでの計算速度も比較してみます。ありがとうございます。専門的な情報を記載していただき、学ぶことがたくさんありました。
プログラミングスキルに関してはまだまだペーペーな域なので、がんばります。

回答No.2

Tasuke22

まったくの個人的な見解ですが。

経済的に余裕があるならmatlabを利用し続けるのは有利と思います。
私も今までに、アッセンブラ、コンパイラ言語、インタプリタなど
かなりの数を扱いましたが、数値解析専用のインタプリタはラクですね。
ただ、数値解析を行う前後の処理で大掛かりなことを行なおうとしたら
実現方法に悩むかもしれません。

最近はプログラミングをしていませんが、行列計算で速度を求めるならば
スーパーコンピュータもやった経験から、マルチコア演算、GPU利用の
演算に非常に興味があります。
matlibがそれらに対応してくれたら話は簡単ですが、対応してくれない
なら自分でやるしか無く、C/C++は手放せないのかな、とも思います。

スーパーコンピュータにはその性能を引き出すべく、専用の言語がありま
すので、GPU演算もライブラリとかが世に出ているのかも知れませんけど。

お礼

そうですね、お金をかけてもいいくらいの速さなら、教授に頼み込めるので、教育のためなら理解してくれると思うので、matlabの使うのを聞いてみます。

ありがとうございました。

回答No.1

Tacosan

普通に考えて, Matlab の方が圧倒的に「遅い」ことはほぼありえないよなぁ.
とりあえず
・「スパース」というのがどのくらい「スパース」なのか
・どのような計算をしたいのか
・あなたのプログラムでは「スパース行列」をどのように記憶しているのか
・あなたのプログラミングスキルはどのくらいなのか
・そもそもあなたの目的はなんなのか
などによって「アドバイス」が変わる可能性があります. 特に最後の点は重要で, たとえば「行列の計算をするプログラムをプリミティブなレベルから組む」ことを目的とするのであれば Matlab はそもそも問題外だし, 逆に「計算ができればいいだけであって『プログラムがくめるようになる』ことは歯牙にもかけていない」というなら Matlab で突き進んでもまったく問題ない.
というわけで, あなたの目的意識はどこにあるんでしょうか?

補足

最大で１００００x１００００のスパースになり、それぞれのrowには２～５個の非ゼロ要素がはいり、diagonalの要素はすべてpositive、off-diagonalの要素はnegativeになります。

連立方程式、Ax=b、のxを求める手段として、直接法のGaussian eliminationを使う事を考えています(diagonal dominanceになるので）。

プログラミング自体はここ２年ぐらいの経験で、この行列計算をCで作っています。行列の大きさは様々になるので、mallocして領域を確保してます。あまり、プログラミングの経験がすくないので、専門的なことはまだ知らないことが多いです。

目的としては、上記にもありますように、連立方程式の解、xを求めることです。それで、Cとmatlabでしたら、どちらがいいのかとなり、質問を投稿しました。