大規模ＬＵ分解(LU factorization, LU decomposition)

１．概要

◆機能概要
　　連立一次方程式(simultaneous linear eqations)をＬＵ分解を用いて解く。
　　行列の係数Ａと右辺値ベクトルｂをファイルから読み込み、
　　Ａｘ＝ｂの連立一次方程式の解ベクトルｘをファイルに出力する。

◆起動引数
　　
　　LUfact.exe [-afile1] [-bfile2] [-xfile3] [-efile4]
　　　　　　　　　　　　　-a (入力)係数のファイル名。　省略値：aij.txt
　　　　　　　　　　　　　-b (入力)右辺値のファイル名。省略値：b.txt
　　　　　　　　　　　　　-x (出力)解ｘファイル名。　　　　省略値：x.txt
　　　　　　　　　　　　　-e (出力)誤差のファイル名。　省略値：err.txt;

◆アルゴリズム概要
　疎行列(sparse matrix)を対象としています。
　計算時間と記憶領域は行数(=列数)と非０の係数の数に依存します。
　線形計画法(linear programming)で使っていた基底行列のＬＵ分解逆行列の計算部分を
　切り出したものなので、メモリを多少余分に使います。
　連立一次方程式に特化することでメモリを節約するよう改良することは可能です。
　ピボット選択には下記文献にあるMarkowitz数を用いてfill-inの削減と安定化を目指しています。

　　　　Uwe H. Suhl, Leena M.Suhl, Computing Sparse LU Factorization
　　　　　for Large-Scale Linear Programming Bases,ORSA J. on Comp. Vol 2, No 4, Fall 1990 PP325-335

　スケーリングを行うとＬＵ分解がさらに安定すると期待できますが、このサンプルでは行っていません。

２．入力ファイル形式

◆項目の間はカンマ','で区切ります。
　　行(列)番号は０始まりです。
　　１カラム目が'#'のレコードはコメントです。読み飛ばします。
　　係数のファイルで係数値＝０のレコードは省略できます。
　　係数のファイルで同じ（行番号,列番号）があると後出レコードを無視します。
　　右辺値のファイルで右辺値＝０のレコードは省略できます。

(1) 係数のファイルの形式
　　　　　　行番号,列番号,係数値

(2) 右辺値のファイルの形式
　　　　　　行番号,右辺値

　例-(1)：係数のファイル　aij.txt
　#行, 列, 値（行,列は０始まり。値＝０のレコードは省略可）
　　 0,　 0,　0.0
　　 0,　 1,　2.0
　　 0,　 2,　3.0
　　 1,　 0, -2.0
　　 1,　 1,　0.0
　　 1,　 2, -4.0
　　 2,　 0,　2.0
　　 2,　 1,　2.0
　　 2,　 2,　4.0

　例-(2)：右辺値のファイル　b.txt
　#行, 値（行は０始まり。値＝０のレコードは省略可）
　　 0, 1
　　 1, 2
　　 2, 3

３．使用方法

◆ダウンロード（ダウンロードのページからもダウンロードできます）

　　 sample08.zip　　 370 KB (379,348 バイト) ソース付き

３．１　インストール

　(1)ダウンロードしたファイルを、任意のディレクトリに解凍します。下記ファイルが解凍されます。

　　　sample08フォルダの内容
　　　(a) 使用許諾契約書.txt
　　　(b) LUfact.exe
　　　(c) run.bat
　　　(d) aij.txt
　　　(e) b.txt
　　　(f) readme.txt

３．２　アンインストール

　(1)インストール時に作成したディレクトリごとファイルを削除します。

３．３　起動方法

　　run.bat またはLUfact.exeを、ダブルクリックして下さい。

４．開発環境

Visual Studio 2005 C++