JPH0221361A - 行列演算処理方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、演算装置、特に各種行列演算命令の処理機能
を有する演算処理装置の行列演算処理方式に関する。

〔従来の技術〕

従来より、行列の逆行列の算出や、連立１次方程式の解
法としては例えば、山内二部他著［電子計算機のための
数値計算法ＩＪ　Ｐ７〜Ｐ２２に示されるように掃き出
し法や、ガウスの消去法が、一般的に知られている。

逆行列の算出は、単位行列をＥとすれば、Ａ・Ｘ＝Ｅと
なる様なＸを求めればよく、それには、辿立−次方程式
ＡＸＪ　−ｅｌ　（Ｘ、はＸの第３列、ｅ、はＥの第１
列）をｊ＝１．２・・・　ｎについて解けばよい。従っ
て、以下の説明では、Ｐ−Ｘ−Ｑを満たす、行列Ｘの算
出について述べる。ここで、Ｐ、Ｑは、それぞれｍ行ｍ
列、ｍ行ｎ　−ｍ列の与えられた行列であり、Ｘは求め
るべき、ｍ行ｎ　−ｍ列の行列である。

掃き出し法では、 なる行列人について、 １）第に行をａｋｋで割る。（ａｋｈをピボットと呼ぶ
） ２）ｊ＝１．２．−＝　　ｍに対しくたｔ！　シｊ　＝
　ｋを除＜）、第１行から第に行のａＪｋ倍を引く。

３）上記１）、２１をに＝１．２．−ｍについて繰り返
す。

という計算を行なう。

ガウスの消去法では、 １）　Ｊ＝　ｋ＋１　、−、　ａ＋に対し、第３行から
第に行のａ＋ｈ／ａｉｈ倍を引く。（ａ　ｋｋをピボッ
トと呼ぶ） ２）上記１）をに＝１．２．−　　ｍ−１について繰り
返す。

という計算を行なう。

掃き出し法においても、ガウスの消去法においても、各
階階のピボット（ａ　ｋｋ）は、″０”であってはなら
ない。また゛０″ではなくても、計算の途中て、ピボッ
トが極く小さな値となることがある。この場合に、この
まま計算を続けることは、２（算の精度上、好ましくな
い。

従って、従来より、ビボノ）・の選択という操作が、必
要であった。

この操作は、例丸ばに回目のピボットを決定する際に、
ａｋｋを無条件にピボットとするのではなく、ｉ＝に、
に＋１．−　　ｍなるｌ１ｌｋの中で、絶対値が最も大
きなものを選択するものである。そして、その要素を含
む行をピボット行とし、第に行とピボット行との間で行
の入れ換えを行なった後、計算を行なう。

この際に、ピボット行の番号ｒ、を覚えておき、掃き出
しが全部終わった後で、入れ換えを行なったｋ（ｋ＝ｍ
−１，・・　１）に対してのみ、結果の第に列と第ｒｋ
列の入れ換えを行なう必要がある。

第６図は、前記の演算を行なうための従来の行列演算処
理装置の一列をブロック図で示したものであり、図にお
いて、（１）は演算対象の行列を記憶する主メモＩＪ　
、＋２１は演算処理を行なう中央処理装置（ＣＰＵ）、
（３１は主メモリ（１）から演算の対象となる行列を読
み出して、保持するベクトルアキュムレータ、（４）は
ピボット選択の履歴を記憶し、演算の最後で、列入れ換
えを行なう際に参照されるコラム・インデックス・テー
ブル（以下Ｃ，Ｉ。

デープルと呼ぶ）である。

第７図にＣ，Ｉテーブルの内容、第８図〜第１０図に、
掃き出し法により、ＰＸ＝Ｑを満たす行列Ｘを求めろ場
合の従来の演算処理方式のフローチャートをそれぞれ示
す。

次に、第８図〜第１０図のフローチャー１・に基づき、
従来の行列演算処理方式について説明する。

なお、ここでは、帰き出し法により、前述したＰ・Ｘ＝
Ｑの方程式を解く場合を例にとって、説明する。

第８図において、まず、演算の対象となる行列Ｐ−Ｑを
主メモリ（１）からベクトルアキュムレータ（３）にロ
ードする（ステップ８１）。次に、ｋ＝１とし、（ステ
ップ８２）第９図に示すフローチャートに従って、ピボ
ット選択を行なう　（ステップ８３）。第９図において
、ピボット選択は、先ず、ａｌｋ（Ｊ−に、に＋１．２
ｍ）の中で絶対値が最大のものを選択し、ビボッ１−値
とする（ステップ９１）。このピボッ１−行の番号ｒｋ
をＣ，Ｉテーブル（４）のに番目要素として登録する（
ステップ９２）。ここで、ピボット値が零であれば、エ
ラーとなる（ステップ９３）。次に、ｒｉとｋとを比較
しくステップ９４）　、ｒｋ　＝にであれば第８図のフ
ローへ戻り、ｒｋｆ−にであれば、行列のに行目とｒｋ
行目を入れ替え（ステップ９５）、第８図のフローへ戻
る。第８図において、上記のピボット選択が行われろと
、ピボット行をピボット値で割る（ステップ８４）。そ
して、ピボット行を除いた全ての行に対して掃き出しを
行なう　（ステップ８５〜８７）。次に列の入れ換え（
ステップ８８）を行なう。列の入れ換えは、第１０図に
示すステップ１０１〜１０５により行なわれる。

即ち、ＣＰ　Ｕ　（２１は、ｋ−１，・・・、＋！１の
各行について、前述したピボット選択を行ない、一連の
掃き出し操作を行なう。掃き出し操作完了後に、ピボッ
ト選択の際に作成したＣＩ子テーブル４）を参照しなが
ら、第１０図に示す、フローチャートに従って、列の入
れ替えを行なう。そしてベクトルアキュムレータ（３）
上の結果を主メモリ（１）にストアして演算を終了する
。

〔発明が解決しようとする課題］ 従来の方式によれば、ピボット選択の際に、各行毎に、
行の入れ替え操作が必要となる可能性がある。

この操作では、ベクトルアキュムレータ内の入れ替え行
の要素群の１つ１つ交換しなければならないため、処理
に時間を要し、演算時間が大きくなるという課題があっ
た。

本発明は、上記のような課題を解消するためになされた
もので、逆行列演算もしくは、係数が等しい複数の連立
１次方程式を高速に処理できる行列演算処理装置を得る
ことを目的とする。

〔課題を解決するための手段〕

本発明に係る行列演算処理方式は、ピボット選択の際に
、前記Ｃ，Ｉテーブルのほかに、各行の行変換状態を記
録しておくためのロウ・インデックステーブル（以下Ｒ
，Ｉテーブルと呼ぶ）を作成するものである。

〔作用〕

ピボット選択により、行の入れ換えの必要性が生じた場
合には、行の各要素を入れ換える代わりに、本発明にお
けるＲ１テーブルの入れ換え行に対応する行番号を入れ
替えておき、演算の最終段階で、とのＲ０Ｉテーブルを
参照しながら、ベクトル１キユムレータ内の結果を主メ
モリに格納する。

〔発明の実施例〕

以下、この発明の一実施例を図について説明する。第１
図において、（１）は主メモリ、（２）は中央演算処理
装置（ＣＰＵ）、（３１は、演算対象となる行列を保持
するベクトルアキュムレータ、（４）は、ＣＩ子テーブ
ル、テーブルのに行目には、ｋ回目のピボット選択にて
、選択された、ピボット行の行番号が書き込まれる。（
５）も前記ＣＩ子テーブル４）と同じく、演算の対象と
なる行列と同じ行数（１）から成り、ピボット選択によ
り行の入れ換えの必要性が生じた場合に、実際の行を入
れ替える代わりに、対応する行の行番号を入れ換えるた
めのＲ０■テーブルである。

また、第２図は、Ｒ，Ｉテーブル（５）の行番号の入れ
換えを示す説明図、第３図〜第５図は、掃き出し法によ
り、Ｐ　−ｘ＝ＱＩｔ’ｆＡｔ＝Ｔ行列Ｘ　ｅ　求メる
場合の、本発明のフローチャートである。

演算の対象となる行列、Ｐ、Ｑはそれぞれ主メモリ＋１
１からベクトルアキュムレータ（３）にロード（ステッ
プ３０）された後、第１回目のピッポット選択を行なう
（ステップ３１〜３３及び第４図）。第１回目のピボッ
ト選択では、ａｌｌ、”！ｌｐａ□の中で絶対値が最も
大きな要素を選び出し、その要素をピボットとしくステ
ップ４１）その要素を含む行がピボット行となる（ステ
ップ４２）。

今、仮にａｒｔがピボットに選ばれたとすれば、１行目
とｒ行目の交換を行なう必要があるが、本発明では、実
際の行の交換を行なう代わりにＲＩ子テーブル５）の１
行目とｒ行目を交換する（ステップ４５）。ＲＩ子テー
ブル５）は、演算がはじまる前に、１行目から順に１，
２．・ｒ、・・・釦の値が初期設定されているから、１
回目のピボット選択により、ＲＩ子テーブル５）の内容
は、１行目から順にｒ、２゜・・　１．・　ｍとなる。

この時、ＣＩ子テーブル４）の１行目は、やはり　ｒ″
となるが、ｒ行目は、そのままである。

２回目以降ｍ　−１回目までのピボット選択についても
同様で、第２図に示す様にＲ回目のピボット選択で、第
０行がピボット行となった場合には、ＲＩ子テーブル５
）の第８行目の内容Ｒ６と第に行目の内容Ｒｋを入れ換
える。

このＣＩ子テーブル４）を使用することにより、１回の
行変換で、ｍ個の要素を交換しなければならなかったも
のが、１要素の交換だけで済ませる事ができる。もしも
、ｆｆ＋−１回のピボット選択で毎回行変換が必要とな
る場合には（ｍ　−１）　　・　（ｎ−１）回分の要素
交換をしなくて済む。

ピボット選択と、ピボット行以外の全ての行に対する掃
き出しが、１〜ｆｆ１行について行なわれた後は、従来
と同様に、ＣＩ子テーブル４）を参照しながら列の入れ
換えが行われるが、この時、行列の各行がどんな順番に
並んでいようが問題と（才ならない。問題となるのは、
ベクトルアキュムレータ（３）内の結果を、主メモリ（
１１にストアする際である。

ベクトルアキュムレータ（３）には、行変換されないま
ま結果が残っているため、ＲＩ子テーブル５）を参照し
ながら、正しい行順でストアする（ステップ３９）必要
がある。即ち、第５図に示す様に、ＲＩ子テーブル５）
のに行目にＲｋが入っていたとすれば、ベクトルアキュ
ムレータ（３）内の行列の第Ｒ３行の要素群を主メモリ
（１）内の行列の第に行にストアする。

なお上記実施例では、ＣＩ子テーブル４１、ＲＩ子テー
ブル５）を主メモ１月１）とは別に設けたものを示した
が、主メモリ（１）内にＣＩ子テーブル４）、およびＲ
Ｉ子テーブル５）を、設けてもよい。

また、上記実施例では、掃き出し法を用いて、ＰＸ＝Ｑ
を満たすＸを求める場合について説明したが、ガウスの
消去法や、その他、行列の行や列の入れ換え操作を要す
る演算にも適用できる。

〔発明の効果〕

以上のように、この発明によれば、行の入れ換え状態を
示ずＲＩ子テーブル設置したために、行の入れ換え操作
を要する行列演算において、入れ換え行を構成する全要
素群を入れ換えなくて済み、ＲＩテーブル内の１要素間
を交換するだけでよいため、演算時間が短縮され、高速
な行列演算が可能となる。

【図面の簡単な説明】

第１図は本発明の一実施例による行列演算処理装置のブ
ロック図。第２図本発明による、行変換状態を記録する
テーブルの説明図、第３図〜第５図は、本発明による掃
き出し法のフローチャー１・、第６図は従来の方式によ
る行列演算処理装置のブロック図、第７図は本発明およ
び従来の方式での行変換履歴を記録するテーブルの説明
図、第８図〜第１０図は、従来の方式による掃き出し法
のフローチャー１・である。 図中、（１１は主メモ’Ｊ　、ｆ２１は、中央処理装置
、（３）はベクトルアキュムレータ、（４）は、Ｃ，Ｉ
テーブル、（５）はＲ，Ｉテーブルを示す。 なお、図中、同一符号は、同−又は相当部分を示す。

Claims (1)

【特許請求の範囲】
1. （１）主メモリと、主メモリから読み出した行列の要素
   データを保持するベクトルアキュムレータと、行列の演
   算を行なう中央処理装置とを備えた行列演算処理装置に
   おいて、行又は列の交換状態を記録するテーブルを設け
   、前記テーブルの内容を書き換えることにより、行又は
   列の交換処理を行なうことを特徴とする行列演算処理方
   式。