(57)【要約】【課題】有限体を要素とする正方行列の三角化におけるリダクション数を削減する。【解決手段】有限体の要素からなる第１正方行列を入力とし、当該第１正方行列を三角化して得られる上三角部分を含む第２正方行列の少なくとも一部の要素を得る過程で、当該第１正方行列に基づく行列の複数の位置の要素を被演算子とした積和演算を行って当該被演算子と異なる位置の要素に対応する積和演算結果を得、当該積和演算結果のリダクションを行う。【選択図】図１
2016212723.tif 000002
【特許請求の範囲】
【請求項１】
有限体の要素からなる第１正方行列を入力とし、前記第１正方行列を三角化して得られる上三角部分を含む第２正方行列の少なくとも一部の要素を得る行列三角化装置であって、
前記第１正方行列に基づく行列の複数の位置の要素を被演算子とした積和演算を行って前記被演算子と異なる位置の要素に対応する積和演算結果を得る積和演算部と、
前記積和演算結果のリダクションを行うリダクション部と、
を有する行列三角化装置。
【請求項２】
請求項１の行列三角化装置であって、
前記第２正方行列は下三角部分を含み、前記下三角部分を含む下三角行列と前記第１正方行列との積が、前記上三角部分を含む上三角行列となり、
前記三角化の過程で零となる要素に前記下三角部分の要素が割り当てられる、行列三角化装置。
【請求項３】
請求項１または２の行列三角化装置であって、
前記三角化の過程は前記第１正方行列の要素に基づく要素Ｘの逆元および要素Ｙの逆元を得る逆元演算過程を含み、
前記要素Ｘおよび要素Ｙは前記有限体の元であり、
ＸＹの逆元（ＸＹ）−１となる値を得る第１逆元演算部と、
前記逆元（ＸＹ）−１となる値と前記要素Ｙとの乗算によって前記要素Ｘの逆元Ｘ−１となる値を得る第２逆元演算部と、
前記逆元（ＸＹ）−１となる値と前記要素Ｘとの乗算によって前記要素Ｙの逆元Ｙ−１となる値を得る第３逆元演算部と、
を有する行列三角化装置。
【請求項４】
請求項１または２の行列三角化装置であって、
前記三角化の過程は前記第１正方行列の要素に基づく要素Ｘ＝ｘαの逆元Ｘ−１＝ｘ−αを得る逆元演算過程を含み、
Ｘおよびｘは前記有限体の元であり、ｃおよびαが正の整数定数であり、１≦α≦ｃであり、事前計算された逆元ｘ−ｃを用いた乗算ｘ−ｃｘｃ−αによって前記要素Ｘの逆元Ｘ−１を得るか、または、α＝１，２，・・・，ｃについて事前計算されたｘ−αを参照してαに対応する前記逆元Ｘ−１＝ｘ−αを得る前記逆元演算過程を行う逆元演算部を有する、行列三角化装置。
【請求項５】
ｎが４以上の整数であり、Ａがｎ×ｎの正方行列であり、Ａｉｊが前記正方行列のｉ行ｊ列の要素であり、ｉ＝０，・・・，ｎ−１であり、ｊ＝０，・・・，ｎ−１であり、
Ａ００：＝Ａ００−１を得る第１逆元演算部と、
ｊ＝１，・・・，ｎ−１についてＡ０ｊ：＝Ａ００Ａ０ｊを得る第１乗算部と、
前記第１乗算部で得られた前記要素Ａ０ｊのリダクションを行う第１リダクション部と、
（１）ｉ＝１，・・・，ｎ−１のそれぞれにおける、
（１−１）ｊ＝１，・・・，ｉ−１について
【数１８】
2016212723.tif 000021
を得る第１積和演算部と、
前記第１積和演算部で得られた前記要素Ａｉｊのリダクションを行う第２リダクション部と、
（１−２）ｊ＝１，・・・，ｎ−１について
【数１９】
2016212723.tif 000022
を得る第２積和演算部と、
前記第２積和演算部で得られた前記要素Ａｉｊのリダクションを行う第３リダクション部と、
（１−３）ｊ＝０，・・・，ｉ−２について
【数２０】
2016212723.tif 000023
を得る第３積和演算部と、
前記第３積和演算部で得られた前記要素Ａｉｊのリダクションを行う第４リダクション部と、
（１−４）Ａｉｉ：＝Ａｉｉ−１を得る第２逆元演算部と、
（１−５）ｊ＝０，・・・，ｉ−１について
Ａｉｊ：＝ＡｉｉＡｉｊを得る第２乗算部と、
前記第２乗算部で得られた前記要素Ａｉｊのリダクションを行う第５リダクション部と、
（１−６）ｊ＝ｊ＋１，・・・，ｎ−１について
Ａｉｊ：＝ＡｉｉＡｉｊを得る第３乗算部と、
前記第３乗算部で得られた前記要素Ａｉｊのリダクションを行う第６リダクション部と、
を有する行列三角化装置。
【請求項６】
ｎが４以上の整数であり、Ａがｎ×ｎの正方行列であり、Ａｉｊが前記正方行列のｉ行ｊ列の要素であり、ｉ＝０，・・・，ｎ−１であり、ｊ＝０，・・・，ｎ−１であり、ｒ：＝ｉ＋１であり、
Ａ００：＝Ａ００−１を得る第１逆元演算部と、
ｊ＝１，・・・，ｎ−１についてＡ０ｊ：＝Ａ００Ａ０ｊを得る第１乗算部と、
前記第１乗算部で得られた前記要素Ａ０ｊのリダクションを行う第１リダクション部と、
（１）奇数ｉ＝１，・・・，ｎ−１のそれぞれにおける、
（１−１）ｊ＝１，・・・，ｉ−１について
【数２１】
2016212723.tif 000024
を得る第１積和演算部と、
前記第１積和演算部で得られた前記要素Ａｉｊのリダクションを行う第２リダクション部と、
（１−１−１）ｊ’＝１，・・・，ｒ−１について
【数２２】
2016212723.tif 000025
を得る第２積和演算部と、
前記第２積和演算部で得られた前記要素Ａｒｊ’のリダクションを行う第３リダクション部と、
（１−２）ｊ＝ｉ，・・・，ｎ−１について
【数２３】
2016212723.tif 000026
を得る第３積和演算部と、
前記第３積和演算部で得られた前記要素Ａｉｊのリダクションを行う第４リダクション部と、
【数２４】
2016212723.tif 000027
を得る第４積和演算部と、
前記第４積和演算部で得られた前記要素Ａｒｒのリダクションを行う第５リダクション部と、
（１−３）ｊ＝０，・・・，ｉ−２について
【数２５】
2016212723.tif 000028
を得る第５積和演算部と、
前記第５積和演算部で得られた前記要素Ａｉｊのリダクションを行う第６リダクション部と、
（１−４）行列式
【数２６】
2016212723.tif 000029
を得る第２逆元演算部と、
前記行列式ｄｅｔのリダクションを行う第７リダクション部と、
（１−５）ｉｎｖ：＝（Ａｉｉｄｅｔ）−１を得る第３逆元演算部と、
（１−６）Ａｉｉ−１：＝ｉｎｖ・ｄｅｔを得る第４逆元演算部と、
前記第４逆元演算部で得られた前記要素Ａｉｉ−１のリダクションを行う第８リダクション部と、
（１−７）ｉｎｖＡｒｒ：＝ｉｎｖ・Ａｉｉ２を得る第５逆元演算部と、
前記第５逆元演算部で得られた前記要素ｉｎｖＡｒｒのリダクションを行う第９リダクション部と、
（１−８）ｊ＝０，・・・，ｉ−１についてＡｉｊ：＝Ａｉｉ−１Ａｉｊを得る第２乗算部と、
前記第２乗算部で得られた前記要素Ａｉｊのリダクションを行う第１０リダクション部と、
（１−９）ｊ＝ｉ＋１，・・・，ｎ−１についてＡｉｊ：＝Ａｉｉ−１Ａｉｊを得る第３乗算部と、
前記第３乗算部で得られた前記要素Ａｉｊのリダクションを行う第１１リダクション部と、
（１−１０）ｊ＝ｒ＋１，・・・，ｎ−１について
【数２７】
2016212723.tif 000030
を得る第６積和演算部と、
前記第６積和演算部で得られた前記要素Ａｒｊのリダクションを行う第１２リダクション部と、
（１−１１）ｊ＝０，・・・，ｉ−１について
【数２８】
2016212723.tif 000031
を得る第７積和演算部と、
前記第７積和演算部で得られた前記要素Ａｒｊのリダクションを行う第１３リダクション部と、
（１−１２）ｊ＝０，・・・，ｒ−１についてＡｒｊ：＝ｉｎｖＡｒｒＡｒｊを得る第４乗算部と、
前記第４乗算部で得られた前記要素Ａｒｊのリダクションを行う第１４リダクション部と、
（１−１３）ｊ＝ｒ＋１，・・・，ｎ−１についてＡｒｊ：＝ｉｎｖＡｒｒＡｒｊを得る第５乗算部と、
前記第５乗算部で得られた前記要素Ａｒｊのリダクションを行う第１５リダクション部と、
を有する行列三角化装置。
【請求項７】
請求項５または６の行列三角化装置であって、
各演算部で得られるｕ≧ｖを満たすＡｕｖに代えてＬｕｖ＝Ａｕｖであるｎ×ｎの正方行列Ｌのｕ行ｖ列要素を得、各演算部で得られたＡｕｖに代えてＬｕｖを用いた演算を行う、行列三角化装置。
【請求項８】
請求項１から７のいずれかの行列三角化装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限体を要素とする正方行列の三角化を行う技術に関する。
【背景技術】
【０００２】
有限体を要素とする正方行列の三角化を行う場合には、少なくとも要素間の演算およびリダクション（除算）が必要である（例えば、非特許文献１，２等参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】池田一貞著、「現代数学の応用」、森北出版、１９７５年３月５日、Ｐ１０７−１０８．
【非特許文献２】森正武、杉原正顕、室田一雄著、「線型計算」、岩波書店、１９９４年２月１０日、Ｐ１−１０．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の三角化方法では、行列の所定の位置の要素を被演算子とする演算を行い、その演算結果によって当該被演算子とした要素を更新する「再帰的な演算」を行う頻度が多い。例えば、従来の三角化方法の一つである「掃き出し法」では、所定の要素の逆元を所定の行に乗算し、それによって得られる行を他の行から減算することで当該他の行を更新する処理を各行について再帰的に繰り返す。行列の要素が有限体の元である場合、行列の要素を更新するたびにリダクションを行わなければならず、三角化のためのリダクション回数が増大してしまう。
【０００５】
本発明の課題は、有限体を要素とする正方行列の三角化におけるリダクション回数を削減することである。
【課題を解決するための手段】
【０００６】
有限体の要素からなる第１正方行列を入力とし、当該第１正方行列を三角化して得られる上三角部分を含む第２正方行列の少なくとも一部の要素を得る過程で、当該第１正方行列に基づく行列の複数の位置の要素を被演算子とした積和演算を行って当該被演算子と異なる位置の要素に対応する積和演算結果を得、当該積和演算結果のリダクションを行う。
【発明の効果】
【０００７】
本発明では、積和演算によってその被演算子と異なる位置の要素に対応する積和演算結果を得る。この積和演算の過程で行列の要素を更新する再帰的な処理は不要であり、積和演算が終了するまでリダクションを行う必要もない。その結果、有限体を要素とする正方行列の三角化におけるリダクション回数を削減できる。
【図面の簡単な説明】
【０００８】
【図１】図１は実施形態の行列三角化装置の機能構成を例示したブロック図である。
【図２】図２は実施形態の行列三角化装置の処理を例示したフロー図である。
【図３】図３は実施形態の行列三角化装置の処理を例示したフロー図である。
【図４】図４は実施形態の行列三角化装置の処理を例示したフロー図である。
【図５】図５は実施形態の行列三角化装置の処理を例示したフロー図である。
【図６】図６は実施形態の行列三角化装置の処理を例示したフロー図である。
【図７】図７は実施形態の行列三角化装置の処理を例示したフロー図である。
【図８】図８は実施形態の行列三角化装置の処理を例示したフロー図である。
【図９】図９は実施形態の行列三角化装置の処理を例示したフロー図である。
【図１０】図１０は実施形態の行列三角化装置の処理を例示したフロー図である。
【図１１】図１１は実施形態の行列三角化装置の処理を例示したフロー図である。
【図１２】図１２は実施形態の行列三角化装置の処理を例示したフロー図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［概要］
まず、概要を説明する。
本形態では、有限体の要素からなる「第１正方行列」を入力とし、「第１正方行列」を三角化して得られる「上三角部分」を含む「第２正方行列」の少なくとも一部の要素を得る。「第２正方行列」の要素も当該有限体の元である。この三角化の過程で「第１正方行列」に基づく行列の複数の位置の要素を被演算子とした積和演算を行って当該被演算子と異なる位置（行および列の少なくとも一方が異なる）の要素に対応する積和演算結果を得、この積和演算結果のリダクションを行う。このような積和演算は線形演算であり、積和演算の過程で行列の要素の更新する再帰的な処理は不要である。そのため、積和演算が終了してからリダクションを行うことができ、有限体を要素とする正方行列の三角化におけるリダクション回数を削減できる。なお「有限体」は素体であってもよいし、拡大体であってもよい。「有限体」が素体である場合の「リダクション」は、法となる素数等の正の整数での剰余演算である。「有限体」が拡大体である場合の「リダクション」は、既約多項式を用いた多項式（拡大体を表す多項式）の変換（既約多項式による除算）である。三角化の過程で上述した積和演算に加えて再帰的な演算が必要な場合には、さらにその再帰的な演算を行ってリダクションを行えばよい。この場合であっても、上述の積和演算を行っているため、再帰的な演算の回数は従来方法よりも大幅に削減でき、リダクション回数も削減できる。
【００１０】
「第２正方行列」は「上三角部分」と零の要素とからなる行列であってもよいし、「上三角部分」と「下三角部分」とを含む正方行列であってもよい。たたし、「下三角部分」を含む下三角行列と「第１正方行列」との積が「上三角部分」を含む上三角行列となる。また、三角化の過程で零となる要素に当該下三角部分の要素を割り当てる処理によって「第２正方行列」を得る。これにより、「下三角部分」を格納する記憶容量を削減できる。この具体例については第１，３実施形態で説明する。
【００１１】
また、三角化の過程は「第１正方行列」の要素に基づく要素Ｘの逆元および要素Ｙの逆元を得る逆元演算過程を含んでもよい。要素Ｘおよび要素Ｙは「有限体」の元である。ＸＹの逆元（ＸＹ）−１となる値を得、逆元（ＸＹ）−１となる値と要素Ｙとの乗算によって要素Ｘの逆元Ｘ−１となる値を得、逆元（ＸＹ）−１となる値と要素Ｘとの乗算によって要素Ｙの逆元Ｙ−１となる値を得てもよい。これにより、１回の逆元（ＸＹ）−１の演算と２回の乗算とによって２個の逆元Ｘ−１およびＹ−１を得ることができる。逆元の演算量は非常に大きく、この方法では２回の逆元演算を行うよりも演算量を削減できる（逆元の効率化１）。この具体例については第３実施形態で説明する。
【００１２】
また三角化の過程が「第１正方行列」の要素に基づく要素Ｘ＝ｘαの逆元Ｘ−１＝ｘ−αを得る逆元演算過程を含む場合、事前計算された逆元ｘ−ｃを用いた乗算ｘ−ｃｘｃ−αによって要素Ｘの逆元Ｘ−１を得る逆元演算過程を行うことができる。ただし、Ｘおよびｘは有限体の元であり、ｃおよびαが正の整数定数であり、１≦α≦ｃである。この場合には、乗算によって逆元を得ることができ、演算量を削減できる（逆元の効率化２）。また、α＝１，２，・・・，ｃについて事前計算されたｘ−αを参照してαに対応する逆元Ｘ−１＝ｘ−αを得てもよい。すなわち、１≦α≦ｃの各整数αについてＸ−１＝ｘ−ｃｘｃ−αは以下のようになる。
【表１】
2016212723.tif 000003
そのため、α＝１，２，・・・，ｃとＸ−１＝ｘ−１，ｘ−２，・・・，ｘ−ｃ（すなわち、ｘ−α）を対応付けた参照サーブルを記憶部に格納しておけば、１回のテーブルの参照によって逆元を得ることができる。この参照テーブルはα＝１，２，・・・，ｃの範囲で用意しておけばよく、サイズも小さい（逆元の効率化３）。これらの具体例については第２実施形態で説明する。
【００１３】
以降、図面を参照して各実施形態を説明する。
〔第１実施形態〕
第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の行列三角化装置１は、入力部１１、出力部１２、記憶部１３、制御部１４、積和演算部１５、逆元演算部１６、乗算部１７、およびリダクション部１８を有する。実施形態の行列三角化装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。入力部１１に入力されたデータおよび各部で得られたデータは記憶部１３に格納され、必要に応じて読み出される。行列三角化装置１は、制御部１４の制御のもとで各処理を実行する。
【００１４】
＜処理＞
図２から図４を用いて本形態の処理を説明する。
≪ステップＳ１１≫
行列三角化装置１の入力部１１に有限体（例えば、位数２の素体またはその素体を基礎体とした拡大体）の元を要素とするｎ×ｎの正方行列Ａが入力され、記憶部１３に格納される。以下では、正方行列Ａのｉ行ｊ列の要素をＡｉｊと表す。ただし、ｎは４以上の整数、ｉ＝０，・・・，ｎ−１、ｊ＝０，・・・，ｎ−１である。
【００１５】
≪ステップＳ１２≫
逆元演算部１６はＡ００を入力とし、Ａ００：＝Ａ００−１を得る。ただし、β１：＝β２はβ２をβ１として設定すること（すなわち、β１にβ２を代入すること）を表す。
【００１６】
≪ステップＳ１３≫
ステップＳ１３のループでは、ｊ＝１，・・・，ｎ−１についてｊを１から１ずつ増加させながら、以下のステップＳ１３１，Ｓ１３２を実行する。
乗算部１７は、Ａ００およびＡ０ｊを入力とし、Ａ０ｊ：＝Ａ００Ａ０ｊを得る（ステップＳ１３１）。リダクション部１８は、ステップＳ１３１で得られたＡ０ｊを入力とし、Ａ０ｊのリダクションを行い、リダクション後の要素Ａ０ｊに更新する（ステップＳ１３２）。
【００１７】
≪ステップＳ１４≫
ステップＳ１４のループでは、ｉ＝１，・・・，ｎ−１のそれぞれについてｉを１から１ずつ増加させながら、以下のステップＳ１４１〜Ｓ１４６を実行する。
【００１８】
［ステップＳ１４１］
ステップＳ１４１のループでは、ｊ＝１，・・・，ｉ−１についてｊを１から１ずつ増加させながら、以下のステップＳ１４１１，Ｓ１４１２を実行する。なお、ｊが存在しない場合にはステップＳ１４１は実行されない（この点はその他のループについても同じである）。
積和演算部１５は、ＡｉｋおよびＡｋｊを入力とし、
【数１】
2016212723.tif 000004
を得る。すなわち、行列の複数の位置の要素ＡｉｋおよびＡｋｊを被演算子とした積和演算を行って当該被演算子ＡｉｋおよびＡｋｊと異なる位置の要素に対応する積和演算結果Ａｉｊを得ている（ステップＳ１４１１）。リダクション部１８は、ステップＳ１４１１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ１４１２）。
【００１９】
［ステップＳ１４２］
ステップＳ１４２のループでは、ｊ＝１，・・・，ｎ−１についてｊを１から１ずつ増加させながら、以下のステップＳ１４２１，Ｓ１４２２が実行される。
積和演算部１５は、ＡｉｋおよびＡｋｊを入力とし、
【数２】
2016212723.tif 000005
を得る。ここでも、行列の複数の位置の要素ＡｉｋおよびＡｋｊを被演算子とした積和演算を行って当該被演算子ＡｉｋおよびＡｋｊと異なる位置の要素に対応する積和演算結果Ａｉｊを得ている（ステップＳ１４２１）。リダクション部１８は、ステップＳ１４２１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ１４２２）。
【００２０】
［ステップＳ１４３］
ステップＳ１４３のループでは、ｊ＝０，・・・，ｉ−２についてｊを０から１ずつ増加させながら、以下のステップＳ１４３１，Ｓ１４３２を実行する。
積和演算部１５は、ＡｉｋおよびＡｋｊを入力とし、
【数３】
2016212723.tif 000006
を得る。ここでも、行列の複数の位置の要素ＡｉｋおよびＡｋｊを被演算子とした積和演算を行って当該被演算子ＡｉｋおよびＡｋｊと異なる位置の要素に対応する積和演算結果Ａｉｊを得ている（ステップＳ１４３１）。リダクション部１８は、ステップＳ１４３１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ１４３２）。
【００２１】
［ステップＳ１４４］
ステップＳ１４４では、逆元演算部１６がＡｉｉを入力とし、Ａｉｉ：＝Ａｉｉ−１を得る（ステップＳ１４４）。
【００２２】
［ステップＳ１４５］
ステップＳ１４５のループでは、ｊ＝０，・・・，ｉ−１についてｊを０から１ずつ増加させながら、以下のステップＳ１４５１，Ｓ１４５２を実行する。
乗算部１７は、ＡｉｉおよびＡｉｊを入力とし、Ａｉｊ：＝ＡｉｉＡｉｊを得る（ステップＳ１４５１）。リダクション部１８は、ステップＳ１４５１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ１４５２）。
【００２３】
［ステップＳ１４６］
ステップＳ１４６のループでは、ｊ＝ｊ＋１，・・・，ｎ−１についてｊをｊ＋１から１ずつ増加させながら、以下のステップＳ１４６１，Ｓ１４６２を実行する。
乗算部１７は、ＡｉｉおよびＡｉｊを入力とし、Ａｉｊ：＝ＡｉｉＡｉｊを得る（ステップＳ１４６１）。リダクション部１８は、ステップＳ１４６１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ１４６２）。
【００２４】
≪ステップＳ１５≫
上述のステップＳ１４のループの後、ステップＳ１５のループが実行される。ステップＳ１５のループでは、出力として必要な行ｉ∈｛１，・・・，ｎ−１｝についてステップＳ１５１が実行される。出力として必要な行ｉは｛１，・・・，ｎ−１｝のすべての要素であってもよいし、その一部の要素（例えば、ｉ＝ｎ−１の要素）であってもよい。
【００２５】
［ステップＳ１５１］
ステップＳ１５１のループでは、ｊ＝０，・・・，ｉ−１についてｊを０から１ずつ増加させながら、以下のステップＳ１５１１，Ｓ１５１２を実行する。
乗算部１７は、ＡｊｊおよびＡｉｊを入力とし、Ａｉｊ：＝ＡｊｊＡｉｊを得る（ステップＳ１５１１）。リダクション部１８は、ステップＳ１５１１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ１５１２）。
【００２６】
≪ステップＳ１６≫
出力部１２は、上述のように得られた要素Ａｉｊ（ただし、ｉ＝０，・・・，ｎ−１であり、ｊ＝０，・・・，ｎ−１）からなるｎ×ｎの正方行列Ｂを出力する。例えば、すべてのｉ＝０，・・・，ｎ−１についてステップＳ１５のループが実行された場合、Ｂは、ＬＡ＝Ａ’を満たすｎ×ｎの下三角行列Ｌの下三角部分とｎ×ｎの上三角行列Ａ’の上三角部分とからなる（すなわち、Ｂ＝Ｌ＋Ａ’）。
【００２７】
〔第２実施形態〕
第１実施形態で説明した処理の逆元演算を前述した「逆元の効率化２」または「逆元の効率化３」によって効率化してもよい。以下では、これまで説明した事項との相違点を中心に説明し、既に説明した事項については同じ参照番号を引用して説明を簡略化する。
【００２８】
＜構成＞
図１に例示するように、本形態の行列三角化装置２は、入力部１１、出力部１２、記憶部１３、制御部１４、積和演算部１５、逆元演算部２６、乗算部１７、およびリダクション部１８を有する。
【００２９】
＜処理＞
第１実施形態との相違点は、ステップＳ１２がステップＳ２２に置換され、ステップＳ１４４がステップＳ２４４に置換される点のみである。ステップＳ２２およびＳ２４４でのＡ００−１およびＡｉｉ−１がそれぞれＡ００−１＝ｘ−α１およびＡｉｉ−１＝ｘ−α２と表現できるとする。ただし、α１およびα２は、それぞれ１≦α１≦ｃおよび１≦α２≦ｃを満たす正の整数である。この場合、逆元演算部２６は、事前計算された逆元ｘ−ｃを用いた乗算ｘ−ｃｘｃ−α１によってＡ００−１を計算し（ステップＳ２２）、乗算ｘ−ｃｘｃ−α２によってＡｉｉ−１を計算する（ステップＳ２４４）。あるいは、逆元演算部２６は、α＝１，２，・・・，ｃについて事前計算されたｘ−αを参照し、ｘ−α１をＡ００−１として得（ステップＳ２２）、ｘ−α２をＡｉｉ−１として得てもよい（ステップＳ２４４）。その他は、第１実施形態と同じである。
【００３０】
〔第３実施形態〕
第１実施形態で説明した処理の逆元演算を前述した「逆元の効率化１」によって効率化してもよい。本形態ではその詳細を例示する。
【００３１】
＜構成＞
図１に例示するように、本形態の行列三角化装置３は、入力部１１、出力部１２、記憶部１３、制御部１４、積和演算部３５、逆元演算部３６、乗算部３７、およびリダクション部３８を有する。
【００３２】
＜処理＞
図５から図９を用いて本形態の処理を説明する。
前述したステップＳ１１、Ｓ１２（またはＳ２２）、およびＳ１３が実行された後、以下のステップＳ３４が実行される。
【００３３】
≪ステップＳ３４≫
ステップＳ３４のループでは、ｉ＝１，・・・，ｎ−１についてｉを１から２ずつ増加させながら（すなわち、奇数ｉについて）、以下のステップＳ３４０〜Ｓ３４９，Ｓ３４ａ〜Ｓ３４ｄを実行する。
【００３４】
［ステップＳ３４０］
ステップＳ３４０では、制御部１４がｒ：＝ｉ＋１を得る（ステップＳ３４０）。
【００３５】
［ステップＳ３４１］
ステップＳ３４１のループでは、ｊ＝１，・・・，ｉ−１についてｊを１から１ずつ増加させながら、以下のステップＳ３４１１，Ｓ３４１２，Ｓ３４１３を実行する。
積和演算部３５は、ＡｉｋおよびＡｋｊを入力とし、
【数４】
2016212723.tif 000007
を得る（ステップＳ３４１１）。リダクション部３８は、ステップＳ３４１１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３４１２）。
ステップＳ３４１３のループでは、ｊ’＝１，・・・，ｒ−１についてｊ’を１から１ずつ増加させながら、以下のステップＳ３４１３ａ，Ｓ３４１３ｂを実行する。
積和演算部３５は、ＡｒｋおよびＡｋｊ’を入力とし、
【数５】
2016212723.tif 000008
を得る（ステップＳ３４１３ａ）。リダクション部３８は、ステップＳ３４１３ａで得られたＡｒｊ’のリダクションを行い、リダクション後の要素Ａｒｊ’に更新する（ステップＳ３４１３ｂ）。
【００３６】
［ステップＳ３４２］
ステップＳ３４２のループでは、ｊ＝ｉ，・・・，ｎ−１についてｊをｉから１ずつ増加させながら、以下のステップＳ３４２１，Ｓ３４２２，Ｓ３４２３，Ｓ３４２４を実行する。
積和演算部３５は、ＡｉｋおよびＡｋｊを入力とし、
【数６】
2016212723.tif 000009
を得る（ステップＳ３４２１）。リダクション部３８は、ステップＳ３４２１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３４２２）。積和演算部３５は、ＡｒｋおよびＡｋｒを入力とし、
【数７】
2016212723.tif 000010
を得る（ステップＳ３４２３）。リダクション部３８は、ステップＳ３４２３で得られたＡｒｒのリダクションを行い、リダクション後の要素Ａｒｒに更新する（ステップＳ３４２４）。
【００３７】
［ステップＳ３４３］
ステップＳ３４３のループでは、ｊ＝０，・・・，ｉ−２についてｊを０から１ずつ増加させながら、以下のステップＳ３４３１，Ｓ３４３２を実行する。
積和演算部３５は、ＡｉｋおよびＡｋｊを入力とし、
【数８】
2016212723.tif 000011
を得る（ステップＳ３４３１）。リダクション部３８は、ステップＳ３４３１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３４３２）。
【００３８】
［ステップＳ３４４］
逆元演算部３６は、Ａｉｉ，Ａｉｒ，Ａｒｉ，Ａｒｒを入力とし、行列式
【数９】
2016212723.tif 000012
を得る（ステップＳ３４４１）。リダクション部３８は、ステップＳ３４４１で得られた行列式ｄｅｔのリダクションを行う（ステップＳ３４４２）。
【００３９】
［ステップＳ３４５］
逆元演算部３６は、Ａｉｉおよびｄｅｔを入力とし、ｉｎｖ：＝（Ａｉｉｄｅｔ）−１を得る（ステップＳ３４５）。
【００４０】
［ステップＳ３４６］
逆元演算部３６は、ｉｎｖおよびｄｅｔを入力とし、Ａｉｉ−１：＝ｉｎｖ・ｄｅｔを得る（ステップＳ３４６１）。リダクション部３８は、ステップＳ３４６１で得られたＡｉｉ−１のリダクションを行う（ステップＳ３４６２）。
【００４１】
［ステップＳ３４７］
逆元演算部３６は、ｉｎｖおよびＡｉｉを入力とし、ｉｎｖＡｒｒ：＝ｉｎｖ・Ａｉｉ２を得る（ステップＳ３４７１）。リダクション部３８は、ステップＳ３４７１で得られたｉｎｖＡｒｒのリダクションを行う（ステップＳ３４７２）。
【００４２】
［ステップＳ３４８］
ステップＳ３４８のループでは、ｊ＝０，・・・，ｉ−１についてｊを０から１ずつ増加させながら、以下のステップＳ３４８１，Ｓ３４８２を実行する。
乗算部３７は、ＡｉｋおよびＡｋｊを入力とし、Ａｉｊ：＝Ａｉｉ−１Ａｉｊを得る（ステップＳ３４８１）。リダクション部３８は、ステップＳ３４８１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３４８２）。
【００４３】
［ステップＳ３４９］
ステップＳ３４９のループでは、ｊ＝ｉ＋１，・・・，ｎ−１についてｊをｉ＋１から１ずつ増加させながら、以下のステップＳ３４９１，Ｓ３４９２を実行する。
乗算部３７は、Ａｉｉ−１およびＡｉｊを入力とし、Ａｉｊ：＝Ａｉｉ−１Ａｉｊを得る（ステップＳ３４９１）。リダクション部３８は、ステップＳ３４９１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３４９２）。
【００４４】
［ステップＳ３４ａ］
ステップＳ３４ａのループでは、ｊ＝ｒ＋１，・・・，ｎ−１についてｊをｒ＋１から１ずつ増加させながら、以下のステップＳ３４ａａ，Ｓ３４ａｂを実行する。
積和演算部３５は、ＡｒｋおよびＡｋｊを入力とし、
【数１０】
2016212723.tif 000013
を得る（ステップＳ３４ａａ）。リダクション部３８は、ステップＳ３４ａａで得られたＡｒｊのリダクションを行い、リダクション後の要素Ａｒｊに更新する（ステップＳ３４ａｂ）。
【００４５】
［ステップＳ３４ｂ］
ステップＳ３４ｂのループでは、ｊ＝０，・・・，ｉ−１についてｊを０から１ずつ増加させながら、以下のステップＳ３４ｂａ，Ｓ３４ｂｂを実行する。
積和演算部３５は、ＡｒｋおよびＡｋｊを入力とし、
【数１１】
2016212723.tif 000014
を得る（ステップＳ３４ｂａ）。リダクション部３８は、ステップＳ３４ｂａで得られたＡｒｊのリダクションを行い、リダクション後の要素Ａｒｊに更新する（ステップＳ３４ｂｂ）。
【００４６】
［ステップＳ３４ｃ］
ステップＳ３４ｃのループでは、ｊ＝０，・・・，ｒ−１についてｊを０から１ずつ増加させながら、以下のステップＳ３４ｃａ，Ｓ３４ｃｂを実行する。
乗算部３７は、ｉｎｖＡｒｒおよびＡｒｊを入力とし、Ａｒｊ：＝ｉｎｖＡｒｒＡｒｊを得る（ステップＳ３４ｃａ）。リダクション部３８は、ステップＳ３４ｃａで得られたＡｒｊのリダクションを行い、リダクション後の要素Ａｒｊに更新する（ステップＳ３４ｃｂ）。
【００４７】
［ステップＳ３４ｄ］
ステップＳ３４ｄのループでは、ｊ＝ｒ＋１，・・・，ｎ−１についてｊをｒ＋１から１ずつ増加させながら、以下のステップＳ３４ｄａ，Ｓ３４ｄｂを実行する。
乗算部３７は、ｉｎｖＡｒｒおよびＡｒｊを入力とし、Ａｒｊ：＝ｉｎｖＡｒｒＡｒｊを得る（ステップＳ３４ｄａ）。リダクション部３８は、ステップＳ３４ｄａで得られたＡｒｊのリダクションを行い、リダクション後の要素Ａｒｊに更新する（ステップＳ３４ｄｂ）。
【００４８】
≪ステップＳ３５≫
制御部１４は、ｎが奇数であるか否かを判定する（ステップＳ３５１）。ここで、ｎが偶数であれば前述のステップＳ１５に進む。一方、ｎが奇数であれば以下のステップＳ３５２〜Ｓ３５７が実行された後、前述のステップＳ１５に進む。
【００４９】
［ステップＳ３５２］
制御部１４はｉ：＝ｎ−１を得る（ステップＳ３５２）。
【００５０】
［ステップＳ３５３］
ステップＳ３５３のループでは、ｊ＝１，・・・，ｉ−１についてｊを１から１ずつ増加させながら、以下のステップＳ３５３１，Ｓ３５３２を実行する。
積和演算部３５は、ＡｉｋおよびＡｋｊを入力とし、
【数１２】
2016212723.tif 000015
を得る（ステップＳ３５３１）。リダクション部１８は、ステップＳ３５３１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３５３２）。
【００５１】
［ステップＳ３５４］
ステップＳ３５４のループでは、ｊ＝ｉ，・・・，ｎ−１についてｊをｉから１ずつ増加させながら、以下のステップＳ３５４１，Ｓ３５４２が実行される。
積和演算部３５は、ＡｉｋおよびＡｋｊを入力とし、
【数１３】
2016212723.tif 000016
を得る（ステップＳ３５４１）。リダクション部１８は、ステップＳ３５４１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３５４２）。
【００５２】
［ステップＳ３５５］
ステップＳ３５５のループでは、ｊ＝０，・・・，ｉ−２についてｊを０から１ずつ増加させながら、以下のステップＳ３５５１，Ｓ３５５２を実行する。
積和演算部３５は、ＡｉｋおよびＡｋｊを入力とし、
【数１４】
2016212723.tif 000017
を得る（ステップＳ３５５１）。リダクション部１８は、ステップＳ１４３１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３５５２）。
【００５３】
［ステップＳ３５６］
ステップＳ３５６のループでは、ｊ＝０，・・・，ｉ−１についてｊを０から１ずつ増加させながら、以下のステップＳ３５６１，Ｓ３５６２を実行する。
乗算部３７は、Ａｉｊ：＝Ａｉｉ−１Ａｉｊを得る（ステップＳ３５６１）。リダクション部１８は、ステップＳ３５６１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３５６２）。
【００５４】
［ステップＳ３５７］
ステップＳ３５７のループでは、ｊ＝ｊ＋１，・・・，ｎ−１についてｊをｊ＋１から１ずつ増加させながら、以下のステップＳ３５７１，Ｓ３５７２を実行する。
乗算部３７は、Ａｉｊ：＝Ａｉｉ−１Ａｉｊを得る（ステップＳ３５７１）。リダクション部１８は、ステップＳ３５７１で得られたＡｉｊのリダクションを行い、リダクション後の要素Ａｉｊに更新する（ステップＳ３５７２）。
【００５５】
〔第４実施形態〕
上述した第１から３実施形態において、各演算部で得られるｕ≧ｖを満たすＡｕｖに代えてＬｕｖ＝Ａｕｖであるｎ×ｎの正方行列Ｌのｕ行ｖ列要素を得、各演算部で得られたＡｕｖに代えてＬｕｖを用いた演算を行ってもよい。以下に、第１実施形態において、各演算部で得られるｕ≧ｖを満たすＡｕｖに代えてＬｕｖ＝Ａｕｖを満たすｎ×ｎの正方行列Ｌのｕ行ｖ列要素を得る例を説明する。
【００５６】
＜構成＞
図１に例示するように、本形態の行列三角化装置４は、入力部１１、出力部１２、記憶部１３、制御部１４、積和演算部４５、逆元演算部４６、乗算部４７、およびリダクション部４８を有する。
【００５７】
＜処理＞
図１０から図１２を用いて本形態の処理を説明する。
前述したステップＳ１１、Ｓ１２（またはＳ２２）が実行された後、以下のステップＳ４３が実行される。
≪ステップＳ４３≫
ステップＳ４３のループでは、ｊ＝１，・・・，ｎ−１についてｊを１から１ずつ増加させながら、以下のステップＳ４３１，Ｓ４３２を実行する。
乗算部４７は、Ａ００およびＡ０ｊを入力とし、Ａ’０ｊ：＝Ａ００Ａ０ｊを得る（ステップＳ１３１）。リダクション部１８は、ステップＳ１３１で得られたＡ’０ｊを入力とし、Ａ’０ｊのリダクションを行い、リダクション後の要素Ａ’０ｊに更新する（ステップＳ４３２）
【００５８】
≪ステップＳ４４≫
ステップＳ４４のループでは、ｉ＝１，・・・，ｎ−１のそれぞれについてｉを１から１ずつ増加させながら、以下のステップＳ４４１〜Ｓ４４６を実行する。
【００５９】
［ステップＳ４４１］
ステップＳ４４１のループでは、ｊ＝１，・・・，ｉ−１についてｊを１から１ずつ増加させながら、以下のステップＳ４４１１，Ｓ４４１２を実行する。
積和演算部４５は、ＬｉｋおよびＡｋｊを入力とし、
【数１５】
2016212723.tif 000018
を得る。ただし、被演算子のＬｉｋが得られていないときはＬｉｋ＝Ａｉｋとする。すなわち、行列の複数の位置の要素ＬｉｋおよびＡｋｊを被演算子とした積和演算を行って当該被演算子ＬｉｋおよびＡｋｊと異なる位置の要素に対応する積和演算結果Ｌｉｊを得ている（ステップＳ４４１１）。リダクション部１８は、ステップＳ４４１１で得られたＬｉｊのリダクションを行い、リダクション後の要素Ｌｉｊに更新する（ステップＳ４４１２）。
【００６０】
［ステップＳ４４２］
ステップＳ４４２のループでは、ｊ＝１，・・・，ｎ−１についてｊを１から１ずつ増加させながら、以下のステップＳ４４１１，Ｓ４４１２が実行される。
積和演算部４５は、Ａ’ｉｋおよびＡ’ｋｊを入力とし、
【数１６】
2016212723.tif 000019
を得る。ただし、被演算子のＡ’ｉｋが得られていないときはＡ’ｉｋ＝Ａｉｋとし、Ａ’ｋｊが得られていないときはＡ’ｋｊ＝Ａｋｊとする。ここでも、行列の複数の位置の要素ＡｉｋおよびＡ’ｋｊを被演算子とした積和演算を行って当該被演算子Ａ’ｉｋおよびＡ’ｋｊと異なる位置の要素に対応する積和演算結果Ａ’ｉｊを得ている（ステップＳ４４２１）。リダクション部１８は、ステップＳ４４２１で得られたＡ’ｉｊのリダクションを行い、リダクション後の要素Ａ’ｉｊに更新する（ステップＳ４４２２）。
【００６１】
［ステップＳ４４３］
ステップＳ４４３のループでは、ｊ＝０，・・・，ｉ−２についてｊを０から１ずつ増加させながら、以下のステップＳ４４３１，Ｓ４４３２を実行する。
積和演算部４５は、ＬｉｋおよびＬｋｊを入力とし、
【数１７】
2016212723.tif 000020
を得る。ただし、被演算子のＬｉｋが得られていないときはＬｉｋ＝Ａｉｋとし、Ｌｋｊが得られていないときはＬｋｊ＝Ａｋｊとする。ここでも、行列の複数の位置の要素ＬｉｋおよびＬｋｊを被演算子とした積和演算を行って当該被演算子ＬｉｋおよびＬｋｊと異なる位置の要素に対応する積和演算結果Ｌｉｊを得ている（ステップＳ４４３１）。リダクション部１８は、ステップＳ４４３１で得られたＬｉｊのリダクションを行い、リダクション後の要素Ｌｉｊに更新する（ステップＳ４４３２）。
【００６２】
［ステップＳ４４４］
ステップＳ４４４では、逆元演算部４６がＡｉｉを入力とし、Ｌｉｉ：＝Ａｉｉ−１を得る（ステップＳ４４４）。
【００６３】
［ステップＳ４４５］
ステップＳ４４５のループでは、ｊ＝０，・・・，ｉ−１についてｊを０から１ずつ増加させながら、以下のステップＳ４４５１，Ｓ４４５２を実行する。
乗算部４７は、ＬｉｉおよびＬｉｊを入力とし、Ｌｉｊ：＝ＬｉｉＬｉｊを得る（ステップＳ４４５１）。リダクション部１８は、ステップＳ４４５１で得られたＬｉｊのリダクションを行い、リダクション後の要素Ｌｉｊに更新する（ステップＳ４４５２）。
【００６４】
［ステップＳ４４６］
ステップＳ４４６のループでは、ｊ＝ｊ＋１，・・・，ｎ−１についてｊをｊ＋１から１ずつ増加させながら、以下のステップＳ４４６１，Ｓ４４６２を実行する。
乗算部４７は、ＬｉｉおよびＡ’ｉｊを入力とし、Ａ’ｉｊ：＝ＬｉｉＡ’ｉｊを得る（ステップＳ４４６１）。リダクション部１８は、ステップＳ４４６１で得られたＡ’ｉｊのリダクションを行い、リダクション後の要素Ａ’ｉｊに更新する（ステップＳ４４６２）。
【００６５】
≪ステップＳ４５≫
上述のステップＳ４４のループの後、ステップＳ４５のループが実行される。ステップＳ４５のループでは、出力として必要な行ｉ∈｛１，・・・，ｎ−１｝についてステップＳ４５１が実行される。出力として必要な行ｉは｛１，・・・，ｎ−１｝のすべての要素であってもよいし、その一部の要素であってもよい。
【００６６】
［ステップＳ４５１］
ステップＳ４５１のループでは、ｊ＝０，・・・，ｉ−１についてｊを０から１ずつ増加させながら、以下のステップＳ４５１１，Ｓ４５１２を実行する。
乗算部４７は、ＬｊｊおよびＬｉｊを入力とし、Ｌｉｊ：＝ＬｊｊＬｉｊを得る（ステップＳ４５１１）。リダクション部１８は、ステップＳ４５１１で得られたＬｉｊのリダクションを行い、リダクション後の要素Ｌｉｊに更新する（ステップＳ４５１２）。
【００６７】
≪ステップＳ４６≫
出力部１２は、上述のように得られた要素Ｌｉｊ（ただし、ｉ＝０，・・・，ｎ−１であり、ｊ＝０，・・・，ｎ−１）からなるｎ×ｎの正方行列Ｌ、および要素Ａ’ｉｊ（ただし、ｉ＝０，・・・，ｎ−１であり、ｊ＝０，・・・，ｎ−１）からなるｎ×ｎの正方行列Ａ’を出力する。例えば、すべてのｉ＝０，・・・，ｎ−１についてステップＳ４５のループが実行された場合、正方行列Ｌ，Ａ’は、それぞれＬＡ＝Ａ’を満たすｎ×ｎの下三角行列Ｌ、およびｎ×ｎの上三角行列Ａ’となる。
【００６８】
＜出力ログの具体例＞
以下に出力ログを例示する。以下の例では、有限体として位数２の素体を基礎体とした２の３次拡大体を用い、リダクションのための既約多項式としてｘ３＋ｘ＋１を用い、ｎ＝４とし、前述したステップＳ１５に相当する再帰的な処理をｉ＝３のみについて実行している。なお、以下では行列の各要素を１０進数で表記している。各要素の値を二進数に変換し、そのＭ桁目（２Ｍ−１の位）の値ηＭ∈｛０，１｝を多項式のＭ−１次の項の係数とし、ｘ３＝ｘ＋１を用いてリダクションした多項式が拡大体の元に対応する。
【００６９】
≪入力行列≫
1 1 1 1
1 2 4 8
1 4 16 64
1 8 64 512
【００７０】
≪第１実施形態の出力ログの例示≫
----- 0: 入力 -------------------------------------
1, 1, 1, 1,
1, 2, 4, 3,
1, 4, 6, 5,
1, 3, 5, 4,
----- 1: 0行目処理済-------------------------------------
1, 1, 1, 1,
1, 2, 4, 3,
1, 4, 6, 5,
1, 3, 5, 4,
----- 2: i 行目 左側-------------------------------------
1, 1, 1, 1,
1, 2, 4, 3,
1, 4, 6, 5,
1, 3, 5, 4,
----- 3: i 行目 対角&右側 -------------------------------------
1, 1, 1, 1,
1, 3, 5, 2,
1, 4, 6, 5,
1, 3, 5, 4,
----- 4: i 行目 下三角部分を計算-------------------------------------
1, 1, 1, 1,
1, 3, 5, 2,
1, 4, 6, 5,
1, 3, 5, 4,
----- 5: i 行目 対角成分の逆元を乗算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
1, 4, 6, 5,
1, 3, 5, 4,
----- 6: i 行目 左側-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
1, 5, 6, 5,
1, 3, 5, 4,
----- 7: i 行目 対角&右側 -------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
1, 5, 3, 2,
1, 3, 5, 4,
----- 8: i 行目 下三角部分を計算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
2, 5, 3, 2,
1, 3, 5, 4,
----- 9: i 行目 対角成分の逆元を乗算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
1, 3, 5, 4,
----- 10: i 行目 左側-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
1, 2, 2, 4,
----- 11: i 行目 対角&右側 -------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
1, 2, 2, 5,
----- 12: i 行目 下三角部分を計算 -------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
3, 4, 2, 5,
----- 13: i 行目 対角成分の逆元を乗算------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
6, 3, 4, 2,
----- 14: 最後の行 計算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
6, 3, 4, 2,
----- 15: 最後の行 対角成分乗算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
6, 1, 5, 2,
----- 16: 出力(基本) -------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
6, 1, 5, 2,
【００７１】
≪第３実施形態の出力ログの例示≫
----- 17: 0行目処理済-------------------------------------
1, 1, 1, 1,
1, 2, 4, 3,
1, 4, 6, 5,
1, 3, 5, 4,
----- 18: i 行目 左側-------------------------------------
1, 1, 1, 1,
1, 2, 4, 3,
1, 4, 6, 5,
1, 3, 5, 4,
----- 19: i + 1 行目 左側 -------------------------------------
1, 1, 1, 1,
1, 2, 4, 3,
1, 5, 6, 5,
1, 3, 5, 4,
----- 20: i 行目 対角 & 右側 -------------------------------------
1, 1, 1, 1,
1, 3, 5, 2,
1, 5, 6, 5,
1, 3, 5, 4,
----- 21: i + 1 行目 対角-------------------------------------
1, 1, 1, 1,
1, 3, 5, 2,
1, 5, 7, 5,
1, 3, 5, 4,
----- 22: i 行目 下三角を計算-------------------------------------
1, 1, 1, 1,
1, 3, 5, 2,
1, 5, 7, 5,
1, 3, 5, 4,
----- 23: i行目の逆元と, i + 1 行目の逆元計算 ----------------------------
1, 1, 1, 1,
1, 6, 5, 2,
1, 5, 6, 5,
1, 3, 5, 4,
----- 24: i行目左側逆元乗算-------------------------------------
1, 1, 1, 1,
6, 6, 5, 2,
1, 5, 6, 5,
1, 3, 5, 4,
----- 25: i行目右側逆元乗算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
1, 5, 6, 5,
1, 3, 5, 4,
----- 26: i + 1 行目 右側 -------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
1, 5, 6, 2,
1, 3, 5, 4,
----- 27: i + 1行目 下三角部分計算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
2, 5, 6, 2,
1, 3, 5, 4,
----- 28: i + 1 行目左側逆元乗算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 2,
1, 3, 5, 4,
----- 29: i + 1 行目右側逆元乗算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
1, 3, 5, 4,
----- 30: 最後の行 計算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
6, 3, 4, 2,
----- 31: 最後の行 対角成分乗算-------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
6, 1, 5, 2,
----- 32: 出力(逆元効率化後) -------------------------------------
1, 1, 1, 1,
6, 6, 3, 7,
7, 3, 6, 7,
6, 1, 5, 2,
【００７２】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７３】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００７４】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００７６】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【００７７】
本発明は、例えば、誤り訂正符号や秘密分散などの暗号分野において、拡大体を要素とする正則行列の逆行列を計算する場合などに利用できる。その他、連立方程式を解く必要のある技術分野（例えば、ロボットアームの駆動制御などのロボット工学分野）や、固有値問題を解く必要のある技術分野（例えば、量子コンピュータの量子回路設計等）にも広く利用できる。
【符号の説明】
【００７８】
１〜４  行列三角化装置
【図１】
2016212723.tif 000032
【図２】
2016212723.tif 000033
【図３】
2016212723.tif 000034
【図４】
2016212723.tif 000035
【図５】
2016212723.tif 000036
【図６】
2016212723.tif 000037
【図７】
2016212723.tif 000038
【図８】
2016212723.tif 000039
【図９】
2016212723.tif 000040
【図１０】
2016212723.tif 000041
【図１１】
2016212723.tif 000042
【図１２】
2016212723.tif 000043