連立一次方程式を解く

質問

A[N×N] × X[N] = B[N]の式が与えられ、
X[N]について解く方法が知りたいです。
しかも、かなり大規模な計算です。

ここでの回答が困難であれば、ホームページや書籍を紹介して欲しいです。
ちなみに英語は分かりません。

連立一次方程式を簡単に解く方法にガウスの消去法がありますが、処理速度、メモリの扱いから言って、現実的ではないですよね。
バンドマトリクスも考えられますが、一応考えている行列は疎行列で対角線付近に非零が多いと思いますが、基本的に任意の行列になると思うので、バンドマトリクスが効果的とも思えません。
で、非ゼロだけを集めメモリ消費をおさえる、スカイライン法というのを知りましたが、どう言うアルゴリズムで、コーディングして良いのかも分かりません。

もしくは、既に数値解析用のライブラリがどこかで開発され、無料で公開されており、スカイライン法や他の解法も使用できるものは無いでしょうか。その時はルーチンの使用方法を教えてくれるとありがたいです。

私のプログラム環境はLinuxでgccかg++を使用しています。
または、SunOSでしょうか？
近々、2Ghz、1GMBになる予定。力技も可能？
また、ネットワークを利用して並列処理をする技術は持ち合わせていませんし、環境もありません。

希望は上記式のNが数万以上の連立一次方程式を解きたいと思っています。億行くかな？

色々探しても数値解析となるとFORTRANに関するものが多いのはなぜ？CやC++では行われないのかな？

回答No.3

noname#11476 · ベストアンサー

英語がダメとのことなのでお知らせしてもどうかと思いましたが、一応知識として伝えておきます。
数値計算ライブラリーとしてはgccをお使いの場合、通常はGSL(GNU scientific library)を使うとよいと思います。
gcc, g++ と同じGNUシリーズですから。

ただ、GSLだとご質問のような大規模な配列には不向きです。やはりこれは昔から伝統的にもっとも良く使われているLINPACKなどの後継にあたるLAPACKを使うのが適当であると思います。
GSLライブラリーの説明でも大規模配列についてはLAPACKを推奨しています。ちなみにNumerical Recipes in Cという本（有名な本です）でも推奨しています。
(LAPACKはアメリカの研究機関が開発したもので、無償で公開しています）

さて、LAPACK自体は元々Fortranで書かれています（これは大型計算機や、スーパーコンピュータなどを使うことを前提とすると、fortranの方が使いやすいからですね。）が、C言語での処理も盛んになっていますので、C言語版もあります。
これは、F2Cというfortran -> Cプログラムへの変換ソフトを使い、更に少し手を入れた物です。

下のURLから、ダウンロードできます。
Ｃ言語版は Related Projects から ../clapack に入ると、C言語版を入手できます。
../lapack++ というC++版もありますが、使うには更にややこしいことになりますので、まずはC言語版で良いかと思います。
現在NIST(アメリカの標準機関、日本の計量研のようなものです）ではTNTという大規模なLAPACKのC++版を作ろうとしていますが、今年の夏にVer. 1.0をリリース予定でまだ公開されていません。

取りあえず使われるのでしたらC言語版が良いと思います。

参考URL：

http://www.netlib.org/lapack/

お礼

遅くなりましたが、LAPACKを使用してみました。
恐ろしく計算速度が速いですね。
環境や、コードの最適化がかなりされているようですね。
1000×1000の係数行列を数秒で計算していました。
ちなみにLinux PIII 500MHz 512MBです。

で、係数行列を増やしたときの計算速度を見てみましたが、
7000×7000ぐらいからスワップを使用し始めたためか、
極端に速度が落ちましたね。

しかし、環境毎にLAPACKをインストールする必要があるため、
プログラムの移植が面倒ですね。
で、ライブラリ(***.a)をコンパイル時にリンクするという方法を取ったら、上手く動作しました。
こんな方法でもいいのかな？

LAPACKの移植性の悪さから見て、TNTと言うのは良いですね。
ヘッダーをインクルードするだけでいいんですかね。
しかも、LAPACKの作成者と同じ人が作っている？
けど、処理速度はLAPACKの方が速いみたいですね。
昔から最適化されつづけた差でしょうか？
ちなみにTNT試しましたが、コンパイルできませんでした。
原因がよくわからないので、ver1.00のリリースを待つかな。

そこで、私は、このLAPACKに勝てるものは無いような気がするので、このLAPACKを使用しようと思います。
ちょっと見てみるとバンドマトリクスも解くことが出来るようなので、それを利用しようと思います。
しかし、ドキュメントを見てみると、引数のサブ対角線？スーパー対角線？という意味がわかんない。
これは、バンドマトリクスを理解する必要がありますね。
自分なりに理解してみるつもりですが、分からなかったらまた質問しちゃうかも。ちょっと、他力本願すぎますかな？

後本ですが、古いバージョンの日本語訳があるようなので、余裕があれば見てみようと思います。

回答No.2

nubou

非対称なので使えませんが変形コレスキー法について修正を

主作業領域は非零で対角にない成分の数をＫとすればＫ／２＋Ｎの数を格納する領域です
既に格納されている行列の非零成分に置き換えるような変形の繰り返しをさせればほぼ既に使用されている領域だけですみます
ただし非零が帯状でないので自分でカスタムプログラムを作らなければなりません
私は８１９２×８１９２対称行列のプログラムを数年前組んだことがあります
ただしすべて非零です
変形コレスキー法をさらに改良しさらに計算量を削減できるアルゴリズムを考案し作りました
すべて非零なのですが少しでも早くしたかったので既存のものを使わなかったのです
すると２倍以上高速で計算できるものができました

あなたの問題は計算時間を短くすると言うことではなく格納領域をいかに必要最小限にするかですね
それとプログラム上で非零の領域の指定方法をどうするかですね
さらに対称でないとやっかいなのは非零の成分が変形の度に零成分の位置に移動する可能性があるということですね

ややこしそうですががんばってください

お礼

ありがとうございます。
コレスキー法は対称行列についてかなり力を発揮する解法のようですね。

今回は使用しないかもしれませんが、対称連立一次方程式を扱うときは是非使用しようと思います。

回答No.1

nubou

Ａは実対称行列ですか？
だとすれば変形コレスキー法が有力です
非零の成分が式で識別できるのなら主として非零の成分の行列の容量が作業領域の容量になります

補足

早速の回答ありがとうございます。
自分なりにコレスキー法について調べて見ました。

コレスキー法は係数行列が対称のときに用いれる手法。
A=LLT -> ここのLTはLの転置行列。
LはLU分解の半分で得ることができる。
後は後退代入法によって解けばよい。

これだと扱いにくい部分があるため、
変形(改訂)コレスキー法がある。
A=LDLTと表す。

これなら、出来そうな気がしますが、対称行列についてですよね。
一応係数をテキスト出力してみましたが、最初は対称行列でしたが、行列に境界条件を反映させると対称行列でなくなってしまいました。
これだと、コレスキー法が適用できませんよね。

あかん、またよく分からなくなってきた。