Title
スパース行列のガウス消去における最適ピボッテング・
アルゴリズムとそのフォトランプログラム
Author(s)
喜屋武, 盛基; 白川, 功; 尾崎, 弘
Citation
琉球大学理工学部紀要. 工学篇 = Bulletin of Science &
Engineering Division, University of the Ryukyus.
Engineering(7): 137-150
Issue Date
1974-03-01
URL
http://hdl.handle.net/20.500.12000/26154
137
ス パ ー ス 行 列 の ガ ウ ス 消 去 に お け る 最 適 ピ ボ ッ テ ン グ ・
ア ル ゴ リ ズ ム と そ の フ ォ ト ラ ン プ ロ グ ラ ム
喜 麗 武 盛 基 *
白 川
功**
尾 崎
弘**
Optimal P
i
v
o
t
i
n
g
Algorithm i
n
Gaussian E
l
i
m
i
n
a
t
i
o
n
f
o
r
S
p
a
r
s
e
Mat
r
i
c
e
s
and i
t
s
FORTRAN Program.
Summary
In the process of solving the linear epuation by the Gaussian EIimination or other comparable technigues， a computational interest is the pivotal ordering of the coefficient matix for the given set of epuations.
This paper describes the algorithm fitfor a large scale sparse matrices. The algorithm is essentially so called "minimum fill-in" but the method to obtain the minimum fill-in is unigue and some other criteria are added in oder to improve the optimality.
comparisions are made with Ghausi method by actual program and results are given.
1
まえがき 連立方程株の解を求める場合に重要なことに，係数 行列をL
/
U
分解するときのピポットの順序決定があ る角 本文では一般の非対称連立方程式をスパース技法を 用いて解く場合の最適なヒ・ポットの順序決定のアノレゴ リズムをのぺ，同アノレゴリズムのFORTRANプログラ ムと，その結果について述べる内2
.
諸定義および定理 ここにあげる定義および定理は文献は〕に示したも の〉うち，特に本文のアルゴリズムに関連のあるもの だけで証明などは略した内主
2
主
_
J
.
.
n次の正方行手)1 A = (aij)に対し てプール行列 X(A)= (xii)をつぎのように定義す る角 nu n u 斗 寸 = 1 j a a a，
n u ， e a ， 、 1 ﹃目、 一 一 j z ( -) 塞ー童」ー_t n次のlE方行列 A = (aij)の任意の aijキOに注目し，行 kおよび到 lに関して何らかの操 受付:1973年10月31日 *琉球大学理工学部電気工学科 *ホ大阪大学工学部電子工学科 作を施し，かっその行および列を取り去って得られる nーl次の正方行列を A・
(k、1)=(aij・
(k，t))と したとき， X (A' (k、1)) =(xij・
(k、))と X (A) =(xii)の各要素に エij・
(k、1)=xij八 (XilVXkj) (2) の関係が成立すれば，この操作をakllこ関する s-pivo・tingといい.位、1をこのs-pivotingにおけるpivotと
いう内た立しVおよび〈はプーノレ和およびプーノレ積の 演算を表わす偽 定 義
3
正方行列 A= (!lij)の任意のak、I 辛Oをpivotとするs-pivotingにおいて， 1)頃序対の集 合Fklを Fkl = {(i，
j) r X ij = 0，
X ij・
(k、1) = 1} (3) で定義し，この各元0
，j)f Fklを，このs-pivoting によるfill-inとu、う内主
J
乞一_!
疋方行列 A = (aij)に対して集合 Ik，
JIを JI= {i r Xil=工} (4) Ik= {j 1 Xkj= 1} (6) が定義する円叉以下では集合M
，N
にたいしてその直 積MxNをMxN=
{
(i，j)I
j
fM
，jfN
}
{ A n u- )138 寄屋武:スパース行列のガウス消去における最適ヒ・ボッテング・アルゴリズムと そのフォートランプログラム で表わし， M x Nの部分集合 (i，N)， (M， j)を (i， N) = {(i， j)
I
j f N} (M， j)= {(i， j)1 ifM} で表わす角 (7) (3) 定 理 1 n次の正方行列A
= (aij)の任意 のaklキOをpivotとするs-pivotinglこよって生ずる fill-inの集合Fkll士 Fkl = {J1 -k} x {Ikー1
}
-
〔
(iA1-k (i，川
u
(
j
A
K
ーl山)}
J
で与えられる角 (9) 皐f
t
5
n 次の正方行~IJ A = (aij)に対応 する向 pivotingグラフG(A)とは節点集合V(G)= SUT， S = {SI，S2， ・，Sn}，T = {tl， t2， ・ー， tn}に関する重みのある無向パイパータイトグラフ G=(V(G); E(G))であり，つぎのような構造を もつものとする内 i) 各Sif SはAの行ilこ各tifTはAの 列 Jにそ れぞれ l対工に対応する内 ii) X(A)=(エij)に対して，工ij=1であるとき， かっそのときに限り(si，tDfE(G)であり，枝(Si， tj)は重みFijをもつものとする" 定 事E 6 n次の正方行列 A=
(aij)に対応 するpivotingグラフG (A)に対して，任意のak1キO をpivotとするs-pivotingにより得られるn-1次の 正方行列をA僑 (k、1)とし，これに対応するpivoting グラフをG'(k、1)=
G (A' (k、1))とする禽このと きGからG・
(k、1)への変換操作を技(Sk，tl)に関す る絡約という内星一塁一_l
Aに対応するpivotingグラフG(A) において F四=砂(空集合)なる校が存在するとき， 任意の技 (sk，t1) (kキp，1キq)に関する縮約により 得られる pivotingグラフ G率 (k、1)においてもFpq • (k、1)=ゆである角 定 理3
pivotingグラフGの互いに隣接する 校(Si，tj)， (Sk， tl) (i =kかつ]キ1;または iキk かつ j=l)に対してFij=Fkl=ゅのとき， pivotingグ ラフ G・
(i、j)およびG'(k、1)は校の重みをも含め て同形である内よって定理 2および定理 3からつぎの 定理を得る内主
I
A
4
併なる重みをもっ校を含むような pivotingグラフGに対して， step1) Go←G， k←工としてつぎへ移れ step2) Goにおいて，任意のFpq=ゆなる枝に対 して αk←p， sk← q としてつぎへ移れ step3) Go←G*
(αk，s
k) としてつぎへ移れ step4) Goに重みが併なる校があればk←k+1と してつぎへ移れ step4) Goに重みがゆなる校があればk←k+1と して step2)へ戻りなければ操作完了角 以上の操作を施して得られるpivotingグラフGoは step2)のp，qの選び方にか〉わらず，重みを合め て同形である角 3 最適ピポッテインク.のアルゴリズム step 1)与えられたn次の正方行列 Aoに対するピ ボッテインググラフをGoとして， G←Go，ム←0， N← n，としてつぎの操作より始める内 step2) N = 1であれば操作完了角N>lのとき， GIこFkl=併なる校(sp，tJ)が存在するかどうかしら べる内もし，存在しなければつぎへ移り，存在すれば， G←G・
(k、1)(
…
(G)ー {Sk，tl} E… …
k…
Pω { (ωωsi， tl)I
si f P (tk)} N←N-1 として step2)をく り返す向 step3) Gにおいて Kl = {(sα， ts) 1 1 Fαs 1 =min (1 FijI
引 を求め (si， tj)f E (G) 1 KI 1 = 1ならば，KI = {(Sk， tt)}として G←G・
(k、1) ム ← ム +I
Fk11 N<-N-1 として step2)へ戻り，1 K2 1> 1ならば，つぎへ 移れ内 step5)各校(sr
， t o) f K2に対して max (1 U Fαj 1 )をI壬 (5r
， t o) f K2 tjr
(sα) える枝 (51，tμ)の集合K3を求め，任意の (5k，t1) f K3に対して琉球大学理工学部紀重要(工学篇〉 ユ39 G←G. (k、1) 記憶容量がnxn個，必要となり処理の範聞もそれだ (5) ム←ム+1 Fkl 1 け広がるので手間もかさみ得策ではない内我々が用
N
←N-l
として Step2) へ戻る いた方法はつぎの通りである向大きさNの l次元配列 IND(N)と非零要素の総数NZの大きさの l次元配列 4. データ構造とフォートランプログラム INZ (NZ)，および NUBF(NZ)で校の接続関係と 前述のパイパータイトグラフで表現されるスパース 枝の重み (Fill.inの数〉を表わし更に処理を簡単にす 行列を電子計算機で処理する場合に重要なことは， デ る目的で INDと INZに対称な JND とJNZを利用 ータ構造と処理技法との関係である向 したので記憶容量は2x (N+NZ)+ NZ 程度必要と 一般にグラフは接続行列で表わすこともできるが， する。これはスパース行列に適したデータ構造である。 次にlOxlOの行列とパイパータイトグラフおよびデータ構造の例を示す角￨
3
I
!
I
I
I
1
l
-
I
1
l
i
l
J
-
J
J
」
-
L
U
-L
J-L
l
S4己じ!
I
ト
l
l
1
1
J
s
s
U
7 7
ア
イ
丁
「
771
~
-
-)プー 1
1
-1
っ一一-1-17
一
司
!
一
一
十
-
T
-
!
っ
1
1
-
!
-
! -K
!
三
日
二
仁
「
L
tL
三三二口
!
ェ
o
i
i
￨
1
J
斗
J
li
i
j
9
S
N -10• NZ帽 16 Sw IND (10)ι2 . 4 . 5 .①. 8 . 10. 11. J:l . 14.入、ミ守、
tl t，
t
s
t
.
t
7
IR¥
J
:
校(4， 5)はIND(4) = 7， IND (4 -1)+ 1 = 6 ， M (6 7〕=iL，1iM(7)=5となり校(4， 5) の重み，すなわち Fil1-inの数は NUBF(7)の中 に収めてあり，値は2となっている内また逆にNUBF (3)=0. すなわち IFI=ゆである NUBFの中の最 初jの技はINZ(3) = 2 = J ， ]ND(2) = 2 • IND(2 -1)=2.INZ(2)=2=Iとなり，校(1，J) = (2. 2)がそれである内この例のように.NUBF(K)又は INZ(K)のKを与えて校(1.J) を求める操作は ~J に頻 繁に現われるので簡単なサブルーチンRETV(K.1.1
)
140 喜屋武:スパース行列のガウス消去における最適ピボッテング・アルゴリズムと そのフォートランプログラム として用いた" 以上説明したデータ構造を基に，前述のアルゴリズ ムをフローチャートにしたのが，次の各々のルーチン である内 つぎに MAINROUTINEの各部の説明を行う偽 ①ARYfま原始データからIND，INZ， JND， JNZを
つくるサブルーチンで原始データは校を(1，1)で表わ
して電子計算機に入カする内前例の 10x10の行列の
場合には(l， 6 ，) (l， 9) ， (2， 2)， (2， 6).
(3， 7)…・・となって合計32の数字である内
② はF‘ill-inの計算で，こ』では2個のサブルーチン
IJFLNとNUBKLNを使う内 IJFLN(1， J， NUB) f主 任意の技 (1，J)を与えてそのFi1l-inの数NUBを計算 し，同時に COMMON領域にある工次元配列IFLN に Fi1l-inの校番号の対をたくわえるサブルーチンで fIow-chart 2に詳細が示してある例 NUBFLN(1， J) は任意の校 (1，J)，のFiII-inの数をCOMMON領 域 中のL次元配列 NUBF(NZ)の適当な場所に収めるサ ブルーチンで詳細はfIow-chart3 Iこ示してある内 f1ow-chart4が MAINROUTINEの 内 部 に あ る Fi1l-inの計算の詳細なフローチャートである角これで すべての枝の FilI-inの 計算を し ， そ の 値 を NUBF (NZ)の中に収容する内 ⑥ Subroutine IFZERO (NZ， N， 1， J， IJYN)は配 列NUBF(NZ)の中から零を見つけ対応する校 (1，J) を与えるルーチンでfIow-chart6に詳細を示す内零が みつかった時IJYN=1， 0がないときIJYN=0とな るのでつぎの判断を経て， KONE(前述のKl，Step3) へ行くか，叉はG* (1、J)をつくって Step2)へもどる ことになる内 ④ Subroutin KONE(NZ
，
KlST，
KCNT)はStep3) のKlを求めるルーチンである"工次元配列 NUBF (NZ)を探索して最少のFi1l-inを持つ枝(1，J)の集合 Klのl次元配列KISTの中に収容し，校の数1Kl r をKCNTとする内詳細はfIow-chart6に示す内 ⑤ KTWO (N， NZ， K1ST， KCNT、KCN2)は 1 Kl 1>1で あ る と き ， 各 々 の 枝 (α戸)
f Kl， (KISTの中に収容されている。〉について消去を行い， その結果できるG*
(α，
s)の各校の重みの最少のも のをK2としてK2STの中に入れ， K2の個数をKCN2 とするルーチンである肉この操作にはいる直前のGを すべこのKlに つ い て の 操 作 が 完 了 す る ま で 保 存 し な け れ ば な ら な い の で ， そ の た め に サ ブ ル ー チ ン ESCAPEを用いた角詳細は割愛する内 ⑤ SubroutineKTHR(N， NZ， K2ST， KCN2， K3) はI
K2 1> 1のとき更に Step6)に示す条件を満す 枝を探すルーチンである内詳細は紙面の都合上割愛す る。 ⑦ IJEIM(I， J， NZ， N， NEWNZ)は任意の校(1，J) をピポットしてE(G・
(1、J))をつくるサプJレーチン で，行列ではI行J
行の消去にあたる操作である内詳 細をflow-chart7に示す内 ③ ADIJ(I， J， NZ， N， NEWN8)は任意に技(1， J) をGに加え新しいグラフをつくるルーチンである内 flow-chart8がその詳細である内 ⑨GHAUSI(NZ， N， K， KlST， KCNT)は，文献 (3)による_HSIEHおよびGHAUSIによるアルゴリズ ムによる順序決定の手法で我々のアルゴリズムとの比 較のために用いた内詳細は flow-hart9に示す肉 ⑬ SubroutinePICTURは 図 工 お よ び 図2のように 結果を図示するためのルーチンである内ヒ・ポットの!J頂 序は外側の番号でも示されるが IORDR，JORDRとし て印字される内 FilI-inは*で示され，非零要素はIで 示される偽またFilI-inの発生する順にIJFLとしてFill -inの枝番号が対で印字される内 6_ 結果の例 Nの値を最大60までのスパースな係数行列について 約40例を実行し， GHAUSIの方法と比較したところ40 例中11例がFill-inの総数で改善されたが我々の方法が GHAUSIより悪い例はまだ工例もみつかっていない角 実行時間については，計算機の都合で大ざっぱにしか 計れなかったが， Fill-inの総和がOかそれに近い場合 には我々の方法が早く， Fill-inの総和が多い場合， 例えば図lおよび図2の場合にはGHAUSIの方法が早 U内、 6. む す び 試みた例がわずか40例であり，これだけでは優劣を 確定的には言えないかも知れないが， 11{?lJ
に改善がみ られたことと，我々の方法が悪い例がまだl例もみつ かっていないということからFill-inの数においては我 々の方法が有利であると去えよう角ただ実行時間にお いては，多少劣る点もあるが，これはFill-inの数にお ける優位とのかねあいできまることである偽例えば数 秒余計にかけてFijl-inの数をl個へらしたとしても， その後で何千何万回と実行する数値解では，計算時聞 がはるかに短縮されることが期待できょう.L
岳
l
， ‘ ， 、0・
・ ‘ . -E Y . ‘ . ‘ t e a-'
・
9 ‘ ， ‘ ‘ e・
2 1 E r e -4 2・
E ， t e、
e -E ‘ ， ‘‘
Z I・
q ・ -4・
-e z -A u-，
.
e z 偽 凶 ・ 色 、 t・
g・
-‘
0・
0・
t a r s -e z 守 1 0・
L u t e z‘
1.
、
。
‘
ge・
4 4 0 Z E s t O 4・
t z e E 4‘
a.
‘
a ， e・
0‘
tf ， 、 ‘.
r
、 z・
' g e t‘
.
g -I e -e g-‘
4・
1・
4・
2・
‘.
-z‘
.
， ‘ -e•
-z・
4・
.• ， ‘ 倫 w a ・，
I . . . ， ' ・ 町 、 r •• (l“ ‘'
“ “・
・ "・
・ 江
ド柚，
.""r町内伊川淵1I) ~IHJn叫 MJ??1. ‘ ・
・ ‘ .
0れ ・
(t‘ ・
O { { ) l・
{
r・
屯 0 " l‘ ・ ・
・
・ ・
・ ‘
・ ・
2‘ ・
t I・
e・ (・
s‘
e・
。
1 ••. "。
‘ "叫
"
0‘ ・“
叫
: : ::
γ :
'
;
;
:
? ; :
: : ;
ァ
: : :::
: : :;:
: : -:ε
: : ::;
;
‘ e・
・
l￡
・
・ ・
・
・
4 r . t (，
.
0 ど 1・
‘
け
・
l O h吃
‘
・
I r ( I ( t( •• 句 E ゐ 1 ζ g・
t，
.
f・ ，
‘
C . ( l C。 ‘
"
O C・
I 1 t H。 ，
・
l‘
g・
L Z t・
2‘
"
酌
l l (，
，
'
‘ ' ‘
-u •"
‘
1・
l I ， 2，
E ι 偽 . . t (l 1 . ' '( ' ・ t U( 屯 ' ‘ 1 ・ ・ t・ ・
t‘
1 I I ( 1 1 1 1 1 1 0、 ，
4，
"
・
.
1 4 I・
t H • q‘ . .
t t・
g‘
t . 竃 : ・ 1・
1 1，
・
e・
1 " I I z、 . ‘ ，-，
I •・ .
t I nl I lt、
s“
‘
v・
1 11・
l .1 t "n { /(‘
4・
d、
e・
'H・
r‘ ・
n‘
E‘
l“ ‘ ・ “‘
・ - 、 .“‘.
o・
E・
P・ ‘ ・ ・ ・‘・
‘ ・ ・ ・ ・&・・
o I tl . C ; t， ，
" tl ( l‘
I II・
2・
6・ ・
e‘
u‘
・
・
z‘ 、 ‘ .‘"
' ‘ ・ ・“・
・ "・
4・ ' " ・
E・
4 川 g・
l '河
、
l : tu・ 内 ・ “ ，..、
- ' . . . ，
t ' ‘ ・ ・
utt“
1 " 同 1 7・ 、 " ，・、
‘ ." 、 ・
3 11、 ' " 嶋
l . ， . . I ' r - o Y h' < I 1・
、 .
1・
.1 1 •.
. .
.
1 • I• ー ー I • 1 /'
.
.
t 1・
I • 11.
11l~n d ~""Illf i()
i
O
・llJj ~Hrl ~""I H . ' f ' O c J l y， " ・ ・ ・
・ ・
i
.
O
・
~.I・"".j・
c・
3・ f t O N '
.
.
・
1 1 10宮 崎 ・ 嗣 ，
a側
S 0 1 11-
，
内
相
， ，
S・ ‘ " . . . c ;
0・ 叫 制的川
1 10 ' 1 柑 S u 3η~Y拘 如 何 じ刊嗣
a c・町 内
、 . ( ) . . . c ;
H l 川川 1 i l1 か い ( f S"曲 ~S { . I) ' " "ζ (. -EZ A・
4•••
・ 凶 ﹄ & . . . . ¥.J '、 ‘ 。 司 船
旬 、 ‘ . .
1 . " )曳 8側 、 . . .
1 1 ' 1 ( 鱒 持 工 〉 遥 2 事 脱会 工 面会 ' ){ . .お 抑142 喜屋武:スパース行列のガウス消去における最適ピポッテング・アルゴリズムと そのフォートランプログラム
.
.
.
‘
ー
_
，
.
.
. 叫 刷 同'OCI・
H・
・
。
.
.
.
・
.
.
.
.，
崎
6"'"‘.，.・ち~，
・
，
，
，
_
-
l
t
"
・
・
1
)
1 11 1'‘0・・，..，~. .46" '/t"U1Utnl・
".J・
・
111 I・
・
‘
1・
・
'1・
H01)O" 0 " " " "."1・
2
1
"
'
.
no-o、
.
.
.
2 1，
，
.
、
.
，・
・
1011111¥1・
2、
1・
111・
1、
'0'1l
2
1
)
1・
9、
，
.
"
，
.
>
t
)
(
)
"，
，
，
，
，
.
，
，
，
‘
"
，
.
.
.
・
ω・
a・
it.，
.
.
.
，
.
.
・
v・
・
・
・
1・
u " 1 I I n 1 I I I • .. J I • • • I，
.
.
.
I I，
，
•
•
."，
.
I I・
t，
.
.
10‘
ω 11 11 I 1211，
，
.
，
.
.
，
，
，
J'"
1
仇.
，
17 s・
2・
a・
a切 a・
lc " 11 • 11)
0
1
)
.
，
1.，
，
.
"
1・
，
.
l' 4' 1. JI1・
11 JU I • JI J' J ...
，
1) J'，
.
a・
3今.
.
，
。
.. )1 Jl 肉，.
，
，
-
.
)， 4 U 7・
1 10・2，
.
・
，
I t s -t I.
.
II • I・
• I‘
.
.
- ・ ・
1 I I I I • • I 1 I 1 ・・-・
，
1I.
・
11'
‘
" •• f 3・
0・
・
-
・
1 - I 1・
• I・
-
・
含
l' 1 I・
• I • I • I '" (11S、
0
.
崎
~心~lfl l'"・M‘
"
IIIOJrrf-lt・
OSA帽 )t.，
・
s￡
附
S1.，.4' I)fF lu・
1・・
s •• .OUT
f
.
・
岨
JSt.州側M・
it，
s
.
-
.
o
・
"
.
.
"
旬
且
れ
向
。
F.11陶u ・....υ"・
e・
f (JIJ'IIL・1"5，
.
.
....pn!tlfIC)lf‘uf 'Hl ・ 1 、~ IJFl. P.'AO PAlw-
・
1StI JIL. M M 肘
・
a・ ・
， ， ，
•••
-a，
。
.
，
.p，
•.
‘
‘
，
a・
.
，
. . ， ， ， ‘
-o
，
a o，
，
‘ ，
-柑 m ・ ? ? B，
，
、
-・
0‘
，
，
a，
e，
•.
，
‘
，
・ 3・
-R 0・
，
K B P -v・
2・
2 内 v a v，
，
a. .
。
- s '
. 。 。
a a，
7 .，
， ， ，
-o n， ， ，
v .
。
. ， ，
. ， .3a，
.
，
，
•.
r 、‘
d・ ・
3 u w. .
‘ ，
a w - a， ..
，
2 2 1 v a ' p u ︾ ・3
'
帽 a F ' 0・
a，
s， 、
・ 局 、 ， 。
m F.
，
，
ι a w‘ ，
n u・
‘
，
，
S S E 司， ， ，
. .
22，
a 国 汀 抽 周 却 伊 U ﹃.
，
v '
"
.
，
a，
a J 酬 JOO&‘'
'
- e••
2. ，
a -嶋 N -a--‘
‘
B a-e
a a E P‘ ，
，
.
a
-. ， ・
e••
，
a-s
M 抽 " ， 叫 M‘ ， . 司
‘ ， .
，
'
，
e M H ・ eM V ? ?・
2，
E 1 .、 ， ， ，
2， ，
，
倫脳 ν . 伺 M ω . . ， e . . .' ，
e .‘
E， ， . ， ‘
‘‘ ， . ， ‘ ，
内
1，
a，
. ， . ， . 司
a
.
a
.
=
•
E-a，
1 2 2角
材
‘
，
a.. ， 1 ・ ・‘ ..
e・
・
‘
J 3，
p
o
-， s・
B・
E・
- a，
.
，
a a，
.
，
. a "
，
P，
s-.
.
，
z ・ ・ 2 2，
.•
， 、
・
4・
、
，
‘
.
2 ・ ?" ・
柄 。
.
， ‘
3・
••••
・
2aE@
z
_
球球大学理工学部紀要(工学篤〉 43 MAIN ROUTINE
②
③
+
CALI CALL ARY④
↓ IORDH←[()1 JORDH←JOJ CALL ADIJく弔
「
l
I
CA比 IFZ日」[干
+
②
J
叱伝ミで
>
呼日
③
YESo
l
'
④
司b ....ー'"'門口~~.~わ
〉
flow -chart 1③
144 喜屋武:スパース行列のカウス消去における最適ピポッテング・アルゴリズムと そのフォートランプログラム
SUBROUTINE l
J
F
L
N
(
1
，J
，NUB)
く
s
叩〉
l
NUB山o
I
一 一 一 ↓ 一 一 一 --町一ーーーーー YE出己
IB~IND (1 NO〈
HETURN ) II=Il十l L.ー_-.ー・・・・・一 一ーーー司ー-_ _ーーーーーーーーーーしーーーーー ーー ーーーーーーー ー・ーー司ーーーーーー-J .JLINEσJ-JA' -J:-'I，
~JOJをペ -:.J。
f 10 w -chart2 -a琉球大学漣工学読紀要〈工学篇〉 146
マ
NO YES IK → IK " 1一
L一
E l -2 J+
一
+
ト
四 一 氾 1 N ア ± N-一
一
= 2 B一
2 N 1一
N 山 町 一 M 川 h 一 L h r I斗
JP"~JP
! 1 flow-chart 2 -b]46
﹁
il--ir
喜屋武:スパース行列のカウス消去における最適ピボッテング・アルゴリズムと そのフォートランプログラムSUBROUT1NE NUBFLN (
1
，
J
)
CALL IJFLN IB = IND (1) flow -chart 3 l琉球大学理工栄部紀要〈工学篇〉
NO
日
山
STAET
1 ==1 ，IA = 1一 日
一寸
K 1A J ==INZ (K)
CALL
NUBFLN (
1
，J)ぐ
E N 0 )f
1
0 w -chart 4 147148 喜屋武:スパース行列のカウス消去における最適ピボッテング・アルゴリズムと そのフオートラシプログラム
SUBROUTINE IFZERO (NZ， N， 101， JOJ， jJYN)
f
!ow . ，_l:ha rt 5
";1ilIWI'T1NEKONE (Ni'.， 1¥1メr，''"<::¥1'
KCNT πK 1
琉球大学理工学部紀要(工学第〕
SUBROUTINE ADIJ (1， J， NZ. N. NEWNZ)
(
子
YES f lll¥¥----川I<.lrt 7①
149f
τ
F
i
丁
、
¥
¥ー一一一一一一ノ -十 J J150 喜屋武:スパース行列のカウス消去における食適ピポッテング・アルゴリズムと そのフォートランプログラム 以上述べた結果から我々の手法の優位性がほゾ確め られたが，さらに確定的にすすめるために，Ghausi等 の文献(2)のアルゴリズムによるプログラムを開発中 であり，つぎの機会に，それと我々との比較報告を行 ないたい内また我々のピポット順序づけの有効性が確 められた後、この方法を利用した巨大行列の数値解法 の開発も残された研究課題の一つである内 謝 辞 おわりにこの研究の遂行にあたり，幾多の便宜と御 支援を下さった大阪大学誌礎工学部嵩忠雄教授，なら びに琉球大学電子計算機室長山下崇教授に深謝しま す角 適Pivotingj順序とこれに付随するパイパータイト・グ ラフ"電子通信学会回路とシステム理論研究会資料 CTn-68 (1973-01)
C
2) H. Y. Hsieb aud M.S Ghausi11A probabilistic approach to optimal pivotin喧 andprediction offill.in for random sp町sematrices" IEEE Trans.
on Circuit Theory， Vol， CT.A， No4， pp329・336July
1972.
C 3) H. Y. Hsieh， M. S. Ghausi， "On optimal.
pivoting algorithm in sparse matirces" IEEE
Trans， on Circuit Theory (Corresp)Vol.CT.19，
pp93・96，Jan.1972
