トップページ > ダウンロード > 大規模LU分解

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

1.概要

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

◆起動引数
  
  LUfact.exe [-afile1] [-bfile2] [-xfile3] [-efile4]
                            -a (入力)係数のファイル名。  省略値:aij.txt
                            -b (入力)右辺値のファイル名。省略値:b.txt
                            -x (出力)解xファイル名。    省略値:x.txt
                            -e (出力)誤差のファイル名。  省略値:err.txt;
 
◆アルゴリズム概要
 疎行列(sparse matrix)を対象としています。
  計算時間と記憶領域は行数(=列数)と非0の係数の数に依存します。
  線形計画法(linear programming)で使っていた基底行列のLU分解逆行列の計算部分を
 切り出したものなので、メモリを多少余分に使います。
  連立一次方程式に特化することでメモリを節約するよう改良することは可能です。
  LU分解時のピボット選択には下記文献にある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

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

2.入力ファイル形式

◆項目の間はカンマ','で区切ります。
    行(列)番号は0始まりです。
    1カラム目が'#'のレコードはコメントです。読み飛ばします。
    係数のファイルで係数値=0のレコードは省略できます。
    係数のファイルで同じ(行番号,列番号)があると後出レコードを無視します。
    右辺値のファイルで右辺値=0のレコードは省略できます。
 
(1) 係数のファイルの形式
              行番号,列番号,係数値
 
(2) 右辺値のファイルの形式
              行番号,右辺値
 
 例-(1):係数のファイル aij.txt
 #行, 列,  値  (行,列は0始まり。値=0のレコードは省略可)
    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始まり。値=0のレコードは省略可)
    0,  1
    1,  2
    2,  3 

3.使用方法

◆ダウンロード(ダウンロードのページからもダウンロードできます)
  
      sample08.zip     84.8 KB (86,837 バイト)  
      sample08.lzh     86.3 KB (88,432 バイト)  

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

              (a)使用許諾契約書.txt
              (b)LUfact.exe
              (c)run.bat
              (d)aij.txt
              (e)b.txt
              (f)readme.txt

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

3.3 起動方法
  2016/12/31 まで実行できます。
 
  run.bat またはLUfact.exeを、ダブルクリックして下さい。

4.開発環境

Visual Studio 2008 C++
Copyright 2011 Sogen System Co.,Ltd. All Rights Reserved.