(57)【特許請求の範囲】
【請求項１】
第１組の連立一次代数方程式および第２組の連立一次代数方程式の同値を判定するコンピュータ・システムで実施される方法であって、ｘｊが未知数、ｅｉｊが係数、ｂｉが量であり、前記未知数、係数および量の間に、
ｅｉ１ｘ１＋ｅｉ２ｘ２＋ｅｉ３ｘ３＋…＋ｅｉｎｘｎ＝ｂｉ（但しｉ＝１、２、…、ｎかつｊ＝１、２、…、ｎ（ｎは未知数の個数））の関係があり、ｌｉｉおよびｒｉが代数式であり、ｋ＝｛１；２｝で、
プロセッサが、
（ｌｉｉ）ｋｘｉ＝（ｒｉ）ｋの形になるまで、前記第１組の連立一次代数方程式、および前記第２組の連立一次代数方程式のそれぞれから、ガウス消去法および後退代入法を使用して前記未知数を消去するステップと、
前記代数式を、前記代数式を構成する文字列内で順次配置された１つまたは複数の項を構成するトークン対の形に再計算する初期ステップであって、各前記トークン対が、オペランドが続く演算子を含む、再計算する初期ステップと、
既約式を得るために、文字列比較を行うための既約形に変換する簡約化規則に従って前記代数式を構成する文字列を、前記既約形に変換してメモリに記憶する初期ステップと、
前記消去するステップが、前記既約形に変換された文字列に対して実行され、
前記未知数のそれぞれについて、積（ｌｉｉ）１＊（ｒｉ）２を構成する第１の文字列と積（ｌｉｉ）２＊（ｒｉ）１を構成する第２の文字列とを比較するステップであって、前記第１の文字列と前記第２の文字列とがすべての前記未知数について一致する場合に、前記第１組の連立一次代数方程式および前記第２組の連立一次代数方程式が同値であると判断すること、
を含む、コンピュータ実施される方法。
【請求項２】
前記簡約化規則が、
前記トークン対を前記代数式を構成する項として識別するステップと、
項として識別された前記トークン対に含まれるオペランドをＡＳＣＩＩ値に従って昇順に配置することによって、定数であるオペランドを前記項の先頭に配置し、変数であるオペランドを前記定数であるオペランドの後に配置するステップと、
前記既約形に変換された項を構成する文字列を形成するために、昇順に配置された前記定数であるオペランドと前記変数であるオペランドに対して、１つまたは複数の前記定数であるオペランド同士の積をとることにより整理し、同一の変数集合を有するすべての項の定数の和をとることにより、前記同一の変数集合を有する一の項の定数として整理し、前記同一の変数集合を有するその他のすべての項を消去するステップと、
前記既約形に変換された代数式を構成する文字列を作るために、前記既約形に変換された項を構成する文字列をそれぞれの変数集合のＡＳＣＩＩ値に従って昇順に再配置するステップと、
を実行することを含む、請求項１に記載のコンピュータ実施される方法。
【請求項３】
第１組の連立一次代数方程式および第２組の連立一次代数方程式の同値を判定するコンピュータ・システムであって、ｘｊが未知数、ｅｉｊが係数、ｂｉが量であり、前記未知数、係数および量の間に、
ｅｉ１ｘ１＋ｅｉ２ｘ２＋ｅｉ３ｘ３＋…＋ｅｉｎｘｎ＝ｂｉ（但しｉ＝１、２、…、ｎかつｊ＝１、２、…、ｎ（ｎは未知数の個数））の関係があり、ｌｉｉおよびｒｉが代数式であり、ｋ＝｛１；２｝で、
プロセッサが、
（ｌｉｉ）ｋｘｉ＝（ｒｉ）ｋの形になるまで、前記第１組の連立一次代数方程式、および前記第２組の連立一次代数方程式のそれぞれから、ガウス消去法および後退代入法を使用して前記未知数を消去する手段と、
前記代数式を、前記代数式を構成する文字列内で順次配置された１つまたは複数の項を構成するトークン対の形に再計算する初期手段であって、各前記トークン対が、オペランドが続く演算子を含む、再計算する初期手段と、
既約式を得るために、文字列比較を行うための既約形に変換する簡約化規則に従って前記代数式を構成する文字列を、前記既約形に変換してメモリに記憶する初期手段と、
前記消去する手段が、前記既約形に変換された文字列に対して実行され、
前記未知数のそれぞれについて、積（ｌｉｉ）１＊（ｒｉ）２を構成する第１の文字列と積（ｌｉｉ）２＊（ｒｉ）１を構成する第２の文字列とを比較する手段であって、前記第１の文字列と前記第２の文字列とがすべての前記未知数について一致する場合に、前記第１組の連立一次代数方程式および前記第２組の連立一次代数方程式が同値であると判断すること、
を含む、コンピュータ・システム。
【請求項４】
前記簡約化規則が、
前記トークン対を前記代数式を構成する項として識別する手段と、
項として識別された前記トークン対に含まれるオペランドをＡＳＣＩＩ値に従って昇順に配置することによって、定数であるオペランドを前記項の先頭に配置し、変数であるオペランドを前記定数であるオペランドの後に配置する手段と、
前記既約形に変換された項を構成する文字列を形成するために、昇順に配置された前記定数であるオペランドと前記変数であるオペランドに対して、１つまたは複数の前記定数であるオペランド同士の積をとることにより整理し、同一の変数集合を有するすべての項の定数の和をとることにより、前記同一の変数集合を有する一の項の定数として整理し、前記同一の変数集合を有するその他のすべての項を消去する手段と、
前記既約形に変換された代数式を構成する文字列を作るために、前記既約形に変換された項を構成する文字列をそれぞれの変数集合のＡＳＣＩＩ値に従って昇順に再配置する手段と、
を実行することを含む、請求項３に記載のコンピュータ・システム。
【請求項５】
コンピュータ・システムにおいて、第１組の連立一次代数方程式および第２組の連立一次代数方程式の同値を判定する方法を実施するコンピュータ・プログラムであって、前記方法が、
ｘｊが未知数、ｅｉｊが係数、ｂｉが量であり、前記未知数、係数および量の間に、
ｅｉ１ｘ１＋ｅｉ２ｘ２＋ｅｉ３ｘ３＋…＋ｅｉｎｘｎ＝ｂｉ（但しｉ＝１、２、…、ｎかつｊ＝１、２、…、ｎ（ｎは未知数の個数））の関係があり、ｌｉｉおよびｒｉが代数式であり、ｋ＝｛１；２｝で、
プロセッサが、
（ｌｉｉ）ｋｘｉ＝（ｒｉ）ｋの形になるまで、前記第１組の連立一次代数方程式、および前記第２組の連立一次代数方程式のそれぞれから、ガウス消去法および後退代入法を使用して前記未知数を消去するステップと、
前記代数式を、前記代数式を構成する文字列内で順次配置された１つまたは複数の項を構成するトークン対の形に再計算する初期ステップであって、各前記トークン対が、オペランドが続く演算子を含む、再計算する初期ステップと、
既約式を得るために、文字列比較を行うための既約形に変換する簡約化規則に従って前記代数式を構成する文字列を、前記既約形に変換してメモリに記憶する初期ステップと、
前記消去するステップが、前記既約形に変換された文字列に対して実行され、
前記未知数のそれぞれについて、積（ｌｉｉ）１＊（ｒｉ）２を構成する第１の文字列と積（ｌｉｉ）２＊（ｒｉ）１を構成する第２の文字列とを比較するステップであって、前記第１の文字列と前記第２の文字列とがすべての前記未知数について一致する場合に、前記第１組の連立一次代数方程式および前記第２組の連立一次代数方程式が同値であると判断すること、
をコンピュータに実行させる、コンピュータ・プログラム。
【請求項６】
前記簡約化規則が、
前記トークン対を前記代数式を構成する項として識別するステップと、
項として識別された前記トークン対に含まれるオペランドをＡＳＣＩＩ値に従って昇順に配置することによって、定数であるオペランドを前記項の先頭に配置し、変数であるオペランドを前記定数であるオペランドの後に配置するステップと、
前記既約形に変換された項を構成する文字列を形成するために、昇順に配置された前記定数であるオペランドと前記変数であるオペランドに対して、１つまたは複数の前記定数であるオペランド同士の積をとることにより整理し、同一の変数集合を有するすべての項の定数の和をとることにより、前記同一の変数集合を有する一の項の定数として整理し、前記同一の変数集合を有するその他のすべての項を消去するステップと、
前記既約形に変換された代数式を構成する文字列を作るために、前記既約形に変換された項を構成する文字列をそれぞれの変数集合のＡＳＣＩＩ値に従って昇順に再配置するステップと、
をコンピュータに実行させることを含む、請求項５に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ実施可能な方法に関し、具体的には、２組の連立一次代数方程式が同値であるかどうかを判定する方法および装置に関する。
【０００２】
【従来の技術】
多くの応用分野で、係数行列に数値要素だけが含まれる連立一次代数方程式（ＳＬＡＥ、Simultaneous Linear Algebraic Equations）の１つまたは複数の系を解く必要が生じる。そのような応用分野には、工学およびシミュレーションのコンピュータ・コードが含まれる。ＳＬＡＥの解は、通常は、周知のガウスの消去法を使用して得られる。したがって、以前の方法では、通常は、２つのそのようなＳＬＡＥ系Ｓ1およびＳ2が解かれ、その解が比較される。しかし、そのような方法は、ＳＬＡＥの一方または両方の条件が不良であるか、計算に使用される数値精度が十分に高くない場合に、必ずしも機能しない。
【０００３】
さらに、そのような方法は、一般に、係数行列要素が代数式であるＳＬＡＥの組、および、解が一般に代数形式であるＳＬＡＥの組を解くことに適合されていない。
【０００４】
【発明が解決しようとする課題】
本発明の目的は、２組の連立一次代数方程式が同値であるかどうかを判定する方法、装置およびコンピュータ・プログラム製品を提供することである。
【０００５】
【課題を解決するための手段】
本発明は、組のそれぞれに複数の代数方程式が含まれる、２組の連立一次代数方程式（ＳＬＥＡ）の同値を判定する、コンピュータ実施される方法を提供する。この方法には、
各ＳＬＡＥを標準的な形に約すステップと、
同値が存在するかどうかを判定するためにＳＬＡＥを比較するステップと
が含まれる。
【０００６】
本発明は、さらに、連立一次代数方程式（ＳＬＥＡ）の第１組と第２組の同値を判定する、コンピュータ実施される方法であって、
各ＳＬＡＥを２部分の標準的な形にするために、ＳＬＡＥの組のそれぞれから未知数を繰り返して消去するステップと、
一方の標準的な形の方程式の一部ともう１つの標準的な形の方程式の別の部分の一部との積を形成するステップと、
標準的な形の方程式の他の部分ともう１つの標準的な形の方程式の他の部分との積を形成するステップと、
数学的同値についてめいめいの積を比較するステップと
を含む方法を提供する。
【０００７】
さらに、連立一次代数方程式の第１組および第２組の同値を判定する、コンピュータ実施される方法であって、ｘjが未知数、ｅijが係数、ｂiが量であるものとして、方程式のそれぞれが、
ｅi1ｘ1＋ｅi2ｘ2＋ｅi3ｘ3＋…＋ｅinｘn＝ｂi
の形である、コンピュータ実施される方法が提供される。係数および量は、既知の代数式である。この方法には、
ｌiiおよびｒiが代数式であり、ｋ＝｛１；２｝が、その方程式がそこから導出された組の１つを示すものとして、方程式のそれぞれが、
（ｌii）kｘi＝（ｒi）k
の形になるまで、連立一次代数方程式の組のそれぞれから未知数を繰り返して消去するステップと、
未知数のそれぞれについて、積（ｌii）1＊（ｒi）2と（ｌii）2＊（ｒi）1とを比較するステップであって、これらの積がすべての未知数について一致する場合に、連立一次代数方程式の第１組および第２組が同値である、比較するステップと
が含まれる。
【０００８】
本発明は、さらに、連立一次代数方程式の第１組と第２組との同値を判定する計算装置であって、ｘjが未知数、ｅijが係数、ｂiが量であり、係数および量が既知の代数方程式であるものとして、方程式のそれぞれが、
ｅi1ｘ1＋ｅi2ｘ2＋ｅi3ｘ3＋…＋ｅinｘn＝ｂi
の形である、計算装置を開示する。この装置には、
ｌiiおよびｒiが代数式であり、ｋ＝｛１；２｝が、その方程式がそこから導出された組の１つを示すものとして、方程式のそれぞれが、
（ｌii）kｘi＝（ｒi）k
の形になるまで、連立一次代数方程式の組のそれぞれから未知数を繰り返して消去する手段と、
未知数のそれぞれについて、積（ｌii）1＊（ｒi）2と（ｌii）2＊（ｒi）1とを比較する手段であって、これらの積がすべての未知数について一致する場合に、連立一次代数方程式の第１組および第２組が同値である、比較する手段と
が含まれる。
【０００９】
本発明は、さらに、連立一次代数方程式の第１組および第２組の同値を判定する、記憶媒体によって担持されるコンピュータ・プログラム製品であって、ｘjが未知数、ｅijが係数、ｂiが量であり、係数および量が、既知の代数式であるものとして、方程式のそれぞれが、
ｅi1ｘ1＋ｅi2ｘ2＋ｅi3ｘ3＋…＋ｅinｘn＝ｂi
の形である、コンピュータ・プログラム製品を開示する。このコンピュータ・プログラム製品には、
ｌiiおよびｒiが代数式であり、ｋ＝｛１；２｝が、その方程式がそこから導出された組の１つを示すものとして、方程式のそれぞれが、
（ｌii）kｘi＝（ｒi）k
の形になるまで、連立一次代数方程式の組のそれぞれから未知数を繰り返して消去するプログラム要素と、
未知数のそれぞれについて、積（ｌii）1＊（ｒi）2と（ｌii）2＊（ｒi）1とを比較するプログラム要素であって、これらの積がすべての未知数について一致する場合に、連立一次代数方程式の第１組および第２組が同値である、比較するプログラム要素と
が含まれる。
【００１０】
この方法には、さらに、代数式を、文字列内で順次配置された１つまたは複数のトークン対の形に再計算するステップであって、トークン対のそれぞれに、演算子とそれに続くオペランドが含まれる、再計算するステップと、既約式を得るために、所定の簡約化規則の組に従って文字列を約するステップとが含まれることが好ましい。連立一次代数方程式の組のそれぞれからの未知数の消去は、所定の動作の組に従って約された文字列に対して実行される。
【００１１】
さらに、簡約化規則に、トークン対をサブグループに配置するステップと、配置されたサブグループのオペランド・トークンを順番に配置するステップと、約されたサブグループを形成するために、１つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約するステップと、約された文字列を作るために、類似するサブグループの１つまたは複数の倍数インスタンスを整理するステップとを含めることができる。
【００１２】
【発明の実施の形態】
本発明の好ましい実施形態を実践することができる汎用のコンピュータ・システム１００を、図１に示す。まずコンピュータ・システム１００を説明し、その後、より具体的に、２組の連立一次代数方程式が同値であるかどうかを判定する方法を説明する。
【００１３】
この方法は、コンピュータ・システム１００内で実行されるアプリケーション・プログラムなどのソフトウェアとして実施することができる。具体的に言うと、２組の連立一次代数方程式が同値であるかどうかを判定する方法のステップは、コンピュータ・システム１００によって実行されるソフトウェア内の命令によって実施される。このソフトウェアは、たとえば下で説明する記憶装置を含む、コンピュータ可読媒体に保管することができる。ソフトウェアは、コンピュータ可読媒体からコンピュータ・システム１００にロードされ、その後、コンピュータ・システム１００によって実行される。そのようなソフトウェアまたはコンピュータ・プログラムをその上に記録されたコンピュータ可読媒体が、コンピュータ・プログラム製品である。コンピュータでのコンピュータ・プログラム製品の使用によって、本発明の実施形態による２組の連立一次代数方程式が同値であるかどうかを判定する有利な装置がもたらされることが好ましい。
【００１４】
コンピュータ・システム１００には、コンピュータ・モジュール１０１と、キーボード１０２およびマウス１０３などの入力装置と、プリンタ１１５およびディスプレイ装置１１４を含む出力装置が含まれる。コンピュータ・モジュール１０１には、通常は、少なくとも１つのプロセッサ１０５と、たとえば半導体のランダム・アクセス・メモリ（ＲＡＭ）および読取専用メモリ（ＲＯＭ）から形成されるメモリ１０６と、ビデオ・インターフェース１０７、プリンタ１１５用の入出力インターフェース、およびキーボード１０２およびマウス１０３用の入出力インターフェース１１３を含む入出力（Ｉ／Ｏ）インターフェースとが含まれる。記憶装置１０９が設けられ、これには、通常は、ハード・ディスク１１０およびフロッピ・ディスク・ドライブ１１１が含まれる。ＣＤ−ＲＯＭドライブ（図示せず）を、データの不揮発性の供給源として設けることができる。コンピュータ・モジュール１０１のプロセッサ１０５、メモリ１０６、ビデオ・インターフェース１０７、記憶装置１０９、ハード・ディスク１１０、フロッピ・ディスク・ドライブ１１１、および入出力インターフェース１１３は、通常は、相互接続されたバス１０４を介して、当業者に既知のコンピュータ・システム１００の動作の従来のモードをもたらす形で通信する。
【００１５】
通常、好ましい実施形他のアプリケーション・プログラムは、ハード・ディスク１１０に常駐し、プロセッサ１０５によって読み取られ、その実行の際に制御される。プログラムの中間記憶を、おそらくはハード・ディスク１１０と共同して、半導体メモリ１０６を使用して達成することができる。いくつかの場合に、アプリケーション・プログラムを、ＣＤ−ＲＯＭまたはフロッピ・ディスクにエンコードしてユーザに供給し、ＣＤ−ＲＯＭドライブ（図示せず）またはフロッピ・ディスク・ドライブ１１１を介して読み取ることができ、その代わりに、モデム装置（図示せず）を介してネットワーク（図示せず）からユーザが読み取ることができる。さらに、ソフトウェアは、磁気テープ、ＲＯＭまたは集積回路、光磁気ディスク、コンピュータ・モジュール１０１と別の装置の間の無線伝送チャネルまたは赤外線伝送チャネル、ＰＣＭＣＩＡカードなどのコンピュータ可読カード、電子メール送信およびウェブサイトなどに記録された情報を含むインターネットおよびイントラネットを含む他のコンピュータ可読媒体からコンピュータ・システム１００にロードすることもできる。前述は、関連するコンピュータ可読媒体の例示にすぎない。他のコンピュータ可読媒体を、本発明の範囲および趣旨から逸脱せずに実践することができる。
【００１６】
本発明のハードウェア環境を説明したので、２組の連立一次代数方程式が同値であるかどうかを判定する方法を説明する。
【００１７】
方法の広義の概要
Ｓが、次式によって与えられる連立一次代数方程式（ＳＬＡＥ）の系を表すものとする。
ｅ11ｘ1＋ｅ12ｘ2＋ｅ13ｘ3＋…＋ｅ1nｘn＝ｂ1
ｅ21ｘ1＋ｅ22ｘ2＋ｅ23ｘ3＋…＋ｅ2nｘn＝ｂ2
…  …  …  …
ｅn1ｘ1＋ｅn2ｘ2＋ｅn3ｘ3＋…＋ｅnnｘn＝ｂn
ここで、ｎ個の未知数｛ｘ1、ｘ2、ｘ3、…、ｘn｝が、ｎ個の方程式によって関連し、係数ｅij（ｉ＝１、２、…、ｎおよびｊ＝１、２、…、ｎ）が、既知の代数式であり、右辺の量ｂi、ｉ＝１、２、…、ｎも代数式である。
【００１８】
そのような２つの系Ｓ1およびＳ2が同値すなわち、めいめいの解が互いに同一であるかどうかを判定する方法は、おおまかに次の２つの部分を有する。
（１）下記の型の標準的な形へのＳＬＡＥの各系Ｓの既約化。
ｌ11ｘ1＝ｒ1
ｌ22ｘ2＝ｒ2
ｌ33ｘ3＝ｒ3
…  …
ｌnnｘn＝ｒn
ここで、ｌiiおよびｒiは代数式である。
（２）２組のＳＬＡＥの標準的な形での比較。
【００１９】
ＳＬＡＥ  Ｓ1およびＳ2の係数ｅijおよび量ｂiが、除算演算子を有しないと仮定する。望ましくない除算演算子は、影響される量に適当な係数を掛けることによって、ＳＬＡＥ  Ｓ1およびＳ2から消去することができる。これは、交換可能な演算子でない除算演算子に関連するオペランドの処理の複雑さを減らすために行われる。
【００２０】
既約式
係数および量を式として記述することができ、係数および量の項には定数および変数を含めることができる。好ましい実施形態では、２つの式の間の比較を容易にするために、下で説明するように、式の既約形という概念を使用した。既約式は、式がそれに変換される標準形である。
【００２１】
変換される式が、構文的に正しく、空白を含まないことが、先験的に仮定される。好ましい実施形態では、変数が、その構成において、小文字の英字、下線文字、および数字に制限され、変数が、数字から始まってはならず、下線で終わってはならない。これらの構成規則が満たされない場合には、影響を受ける変数を、構成規則に従う代替であるが別個の変数にマッピングする（別名を割り当てる）ことができ、これらの新しい変数が、その代わりに使用される。
【００２２】
この実施形態で採用された規則は、正整数のべきである係数ｅijおよび量ｂiの変数を、変数の掛け算として書き出すことである。したがって、たとえば
ａnは、ａ＊ａ＊…＊ａになる。ここで、ａはこの積にｎ回現れる。
【００２３】
所与の式を既約式に変換するために、式を、まず次の形にする。
＜単項演算子＞＜オペランド＞＜演算子＞＜オペランド＞…＜演算子＞＜オペランド＞
ここで、単項演算子は、＋（プラス）または−（マイナス）のいずれかであり、各演算子は、＋（加算）、−（減算）、または＊（乗算）の１つである。式が単項演算子から始まらない場合には、単項演算子＋（プラス）を式の先頭に挿入する。たとえば
ａ＋ｂ＊ｃ−ｄは、＋ａ＋ｂ＊ｃ−ｄになる。
【００２４】
特に、括弧がないことに留意されたい。括弧が式中に存在する場合には、２つの括弧で囲まれた係数を掛ける、余分な括弧を無視するなど、括弧を除去するのに必要な演算を実行することによって括弧を除去して、所与の式を上の形にしなければならない。
【００２５】
次に、すべての＋（加算）演算子は、文字列＋１＊によって置換され、その結果、＋が＋１＊になる。同様に、すべての−（減算）演算子は、文字列−１＊によって置換され、その結果、−が−１＊になる。したがって、たとえば
＋ａは、＋１＊ａになり
−ａ＊ｂは、−１＊ａ＊ｂになる。
【００２６】
最後に、定数（前のステップで導入される１を含む）であるオペランドは、次のｅ形式に変換される。
”．［符号なし数］ｅ［ｅ符号］［符号なし指数］”
ここで、［符号なし数］は、数字だけを含むｎ桁の数であり、ｎは、０より大きいプレフィックスト整数である。
［ｅ符号］は、指数の符号であり、プラスの場合は＞、マイナスの場合は＜になる。
［符号なし指数］は、数字だけを含むｍ桁の数であり、ｍは、０より大きいプレフィックスト整数である。
【００２７】
したがって、たとえば、
２５＝０．２５＊１０2は、．２５００００ｅ＞０２になり、
０．０２５＝０．２５＊１０-1は、．２５００００ｅ＜０１になる。
ここでは、ｎ＝６、ｍ＝２であると仮定する。すべての定数が、ｅ形式では一定の長さｍ＋ｎ＋３文字の文字列によって表されることに留意されたい。ここで、ｅ［ｅ符号］［符号なし指数］は、１０の［ｅ符号］［符号なし指数］乗を表し、実際の定数を得るためには．［符号なし数］によって表される数をかけなければならない。
【００２８】
式には、定数である少なくとも１つのオペランドが含まれることになる。各式は、１つまたは複数の項を有し、各項は、次の形を有する。
＜単項演算子＞＜オペランド＞＜＊＞＜オペランド＞…＜＊＞＜オペランド＞
ここで、単項演算子は、＋（プラス）または−（マイナス）であり、２つの連続するオペランドの間に、乗算演算子＊がある。項を識別した後に、各定数の［ｅ符号］を、＜または＞から−または＋に復元する。
【００２９】
各項では、オペランドが、そのＡＳＣＩＩ（情報交換用米国標準コード）値に従って、昇順でソート（再配置）される。乗算演算子が交換可能な演算子であり、したがって、オペランドの交換が完全に許容可能であるから、これは項に影響しない。定数であるオペランドは、すべてが項の先頭に集められ、その位置で、オペランドを簡単に識別でき、単一の定数によって置換することができる。したがって、たとえば、
＋．１０００００ｅ＋０１＊ａ＊ｂ＊．５０００００ｅ＋００
は、オペランドを昇順で配置した後に、
＋．１０００００ｅ＋０１＊．５０００００ｅ＋００＊ａ＊ｂ
になり、定数を整理した後に、
＋．５０００００ｅ＋００＊ａ＊ｂ
になる。
【００３０】
この段階で、項は、次の形を有する。
＜単項演算子＞＜定数＞＜＊＞＜オペランド＞…＜＊＞＜オペランド＞
ここで、各オペランドは、変数であり、そのＡＳＣＩＩ値は、後続のオペランドがある場合に、それより小さくない。これが、項の既約形である。既約形では、項の非定数部分を変数グループと呼ぶ。たとえば、既約形の項が「＋．２５００００ｅ＋０１＊ａ＊ａ＊ｂ」である場合には、その変数グループは「＊ａ＊ａ＊ｂ」である。
【００３１】
式では、変数グループが一致するすべての項が、項の１つの定数を変更し、同一の変数グループを有する他のすべての項を消去することによって組み合わされる。
【００３２】
最後に、式の既約項を、そのめいめいの変数グループのＡＳＣＩＩ値に従って、昇順で再配置する。この最終形では、式が、その既約形であるという。特に、既約式のどの２つの項も、同一の変数グループを有しないことに留意されたい。
【００３３】
同値を判定する方法
図２を参照すると、２つのそのような系Ｓ1およびＳ2が同値であるかどうかを判定する方法２００が示されている。ステップ２４０から開始して、すべての係数ｅijおよび量ｂiを、そのめいめいの既約形（上で説明した）に変換する。
【００３４】
ステップ２５０ないし２８０では、ガウス消去法および後退代入法（除算をなくすように適合された）を使用して、ＳＬＡＥ  Ｓ1およびＳ2を標準的な形にする。
【００３５】
ステップ２５０では、カウンタｋに１をセットする。次のステップ２５２では、変数ｘkを、第ｊ方程式（ｊ＝（ｋ＋１）、…、ｎ）から消去して、第ｋ導出系を得る。具体的に言うと、カウンタｋが１に等しい状態で、変数ｘ1を、第ｊ方程式（ｊ＝２、３、…、ｎ）から消去して、次のように定義される第１導出系を得る。
ｅ11ｘ1＋ｅ12ｘ2＋ｅ13ｘ3＋…＋ｅ1nｘn＝ｂ1
1ｅ22ｘ2＋1ｅ23ｘ3＋…＋1ｅ2nｘn＝1ｂ2
…  …  …  …  …
1ｅn2ｘ2＋1ｅn3ｘ3＋…＋1ｅnnｘn＝1ｂn
ここで、第１導出系の新しい係数1ｅjkは、次式によって与えられる。
1ｅjk＝ｅjkｅ11ｅ1kｅj1  および
1ｂj＝ｂjｅ11−ｂ1ｅj1  ただし、（ｊ、ｋ）＝２、…、ｎ
【００３６】
係数ｅ11＝０の場合には、系Ｓの第１方程式を、係数ｅ1mが非ゼロの系Ｓの他の方程式ｍと交換する。そのような方程式ｍが見つからない場合には、ＳＬＡＥが特異であり、方法２００、具体的にはステップ２５２が、その下のステップ２７０への線２６２に従うことよって割り込まれ、ステップ２７０で、方法２００が、適当なエラー・メッセージと共に終了する。
【００３７】
ステップ２６０では、カウンタｋがｎ−１と等しいかどうかを判定する。ここで、ｎは未知数の数である。そうではない場合には、ステップ２５５で、第ｋ導出系から副系を定義する。たとえば、カウンタｋが１に等しい場合に、第１導出系から導出される副系は、次の通りである。
1ｅ22ｘ2＋1ｅ23ｘ3＋…＋1ｅ2nｘn＝1ｂ2
…  …  …  …  …
1ｅn2ｘ2＋1ｅn3ｘ3＋…＋1ｅnnｘn＝1ｂn
【００３８】
この副系は、（ｎ−１）個のＳＬＡＥの組であり、（ｎ−１）個の未知数｛ｘ2、ｘ3、…、ｘn｝を有する。ステップ２５８でカウンタｋを増分した後に、系Ｓが次のように第（ｎ−１）導出系に約されるまで、既約化のステップ２５２ないし２６０を副系に対して繰り返す。
0003928921.tif 000002
ここで、対角係数j-1ｅjj  （ｊ＝１、…、ｎ）は、すべてが非ゼロであり、
1ｅjk＝l-1ｅjkl-1ｅll−l-1ｅlkl-1ｅjl
1ｂj＝l-1ｂjl-1ｅlll-1ｂll-1ｅjl  ただしｌ＝１、…、ｎ−１；  （ｊ、ｋ）＝ｌ＋１、…、ｎ
および
0ｅjk＝ｅjk
である。
【００３９】
これで、この処理のガウス消去段階が完了する。この処理全体に除算がないことに留意されたい。カウンタｋは、現在、ｎ−１に等しく、したがって、この方法は、ステップ２８０に継続し、そこで、やはり除算なしで後退代入を実行する。したがって、未知数ｘiを計算するのではなく、積ｌiiｘiを計算する。ここで、ｎ個の未知数ｘiのそれぞれが、ｒiが分子、ｌiiが分母である比ｘ1＝ｒi／ｌiiの形で表される。ｉ＝ｎの場合に、次式が得られる。
n-1ｅnnｘn＝n-1ｂn
その結果、
ｌnn＝n-1ｅnn  および  ｒn＝n-1ｂn
になる。
【００４０】
ｉ＝ｎ−１について、第（ｎ−１）方程式に分母ｌnnを掛けて、
ｌnnn-2ｅn-1,n-1ｘn-1＋ｌnnn-2ｅn-1,nｘn＝n-2ｂn-1ｌnn
または
ｌnnn-2ｅn-1,n-1ｘn-1＝n-2ｂn-1ｌnn−n-2ｅn-1,nｒn
を得る。その結果、
ｌn-1,n-1＝ｌnnn-2ｅn-1,n-1  および  ｒn-1＝n-2ｂn-1ｌnn−n-2ｅn-1,nｒn
になる。
【００４１】
ｉ＝ｎ−２について、第（ｎ−２）方程式に分母ｌn-1,n-1を掛け、
ｌn-1,n-1n-3ｅn-2ｘn-2＋ｌn-1,n-1n-3ｅn-2,n-1ｘn-1＋ｌn-1,n-1n-3ｅn-2,nｘn＝n-3ｂn-2ｌn-1,n-1
または
ｌn-1,n-1n-3ｅn-2,n-2ｘn-2＝n-3ｂn-2ｌn-1,n-1−n-2ｅn-1,n-1n-3ｅn-2,nｒn−n-3ｅn-2,n-1ｒn-1
を得る。その結果、
ｌn-2,n-2＝ｌn-1,n-1n-3ｅn-2,n-2  および  ｒn-2＝n-3ｂn-2ｌn-1,n-1−n-2ｅn-1,n-1n-3ｅn-2,nｒn−n-3ｅn-2,n-1ｒn-1
になる。
【００４２】
すべてのｉ＝１、２、…、ｎ−１について、結果が
ｌii＝ｌi+1,i+1i-1ｅii  および  ｒi＝i-1ｂiｌi+1,1+1−Ｒinｒn−Ｒi,n-1ｒn-1−…−Ｒi,i+1ｒi+1
になり、
ｌnn＝n-1ｅnn  および  ｒn＝n-1ｂn
であることを示すことができる。ここで
Ｒij＝（ｌi+1,i+1／ｌjj）i-1ｅij    ただし、ｊ＝ｎ、…、（ｉ＋１）、ｉ＝１、２、…、ｎ−１
である。
【００４３】
ｌjjが、ｌi+1,i+1の因数なので、Ｒijが除算と無関係になることに留意されたい。しかし、後退代入のステップ２８０に、ｌiiとｒiに共通する因数を消去するステップがないことに留意されたい。
【００４４】
２つのＳＬＡＥ系Ｓ1およびＳ2のそれぞれについてステップ２４０ないし２８０を完了した後に、系Ｓ1の文字列配列（ｌii）1および（ｒi）1と系Ｓ2の（ｌii）2および（ｒi）2が作られている。原則として、２つの系Ｓ1およびＳ2が同値であることを示すためには、それらのめいめいの文字列配列ｌiiおよびｒiが一致することが示されるならば十分である。しかし、一般に、現在既知の方法によってそれらに共通する因数を完全に消去することが不可能なので、これは必ずしも可能ではない。したがって、消去されない共通の因数が存在する可能性があることを前提にしなければならない。しかし、数学的に、
（ｌii／ｒi）1＝（ｌii／ｒi）2
または、これと同等であるが、
（ｌii）1＊（ｒi）2＝（ｌii）2＊（ｒi）1
であることが明らかであり、この形で比較を実行することができる。したがって、ステップ２９０で、ｉ＝１、…、ｎのそれぞれについて、式（ｌii）1＊（ｒi）2および（ｌii）2＊（ｒi）1を計算する。すべての式（ｌii）1＊（ｒi）2および（ｌii）2＊（ｒi）1が、一貫性のある形でその既約形に約された場合には、ステップ３００で、（ｌii）1＊（ｒi）2と（ｌii）2＊（ｒi）1の単純な文字列比較を実行する。判断ステップ３１０で、すべてのｉ＝１、…、ｎについて一致が見つかったかどうかを判定する。回答が肯定の場合には、系Ｓ1およびＳ2の同値を、ステップ３１２で報告する。そうでない場合には、ステップ３１５で非同値を報告する。
【００４５】
例
方法２００を実行して２つの系Ｓ1およびＳ2が同値であるかどうかを判定する例を、これから説明する。ＣおよびＣ＋＋プログラミング言語の表記を使用する。この表記では、係数および量を、それぞれｅ［ｉ−１］［ｊ−１］およびｂ［ｉ−１］と表記する。
【００４６】
下に示す例を理解するために、以下の擬似コード片の参照が役に立つであろう。変数ｅ［］［］およびｂ［］は、なかんずくそのような式に対する演算子＋（加算）、−（減算）、および＊（乗算）演算子を実施する代数式データ型（datatype algebraic expression）を有する。クラスexpressionは、代数式を既約形に変換できるメソッドも有する。
0003928921.tif 000003
0003928921.tif 000004
【００４７】
ここで、系Ｓ1が、次の方程式の組であるものとする。
ａｘ1＋ｘ2＋ｘ3＝ａ＋２
ｘ1＋ｘ2＋ｘ3＝３
ｘ1＋ｘ2−ｘ3＝１
また、系Ｓ2が、次の方程式の組であるものとする。
ａｘ1＋２ｘ2＝ａ＋２
２ｘ1＋２ｘ2＝４
ｘ2−ｘ3＝０
すなわち、各組が３つの方程式からなる。
【００４８】
まず系Ｓ1を検討すると、係数および量を次のように記述することができる。
ｅ［０］［０］＝ａ
ｅ［０］［１］＝１
ｅ［０］［２］＝１
ｂ［０］＝ａ＋２
ｅ［１］［０］＝１
ｅ［１］［１］＝１
ｅ［１］［２］＝１
ｂ［１］＝３
ｅ［２］［０］＝１
ｅ［２］［１］＝１
ｅ［２］［２］＝−１
ｂ［２］＝１
【００４９】
系Ｓ1でステップ２４０を実行することによって、下記のように、係数および量のすべての項が、方法２００を実行するコンピュータ・プログラムによって既約形に変換される。計算の異なる段階で擬似コード変数によって参照されるテキスト変数を、右側に示す。
既約形                                                      変数
ｅ［０］［０］＝＋．１００００ｅ＋０１＊ａ                  0ｅ11＝ｅ11
ｅ［０］［１］＝＋．１００００ｅ＋０１                      0ｅ12＝ｅ12
ｅ［０］［２］＝＋．１００００ｅ＋０１                      0ｅ13＝ｅ13
ｂ［０］＝＋．１００００ｅ＋０１＊ａ＋．２００００ｅ＋０１  0ｂ1＝ｂ1
ｅ［１］［０］＝＋．１００００ｅ＋０１                      0ｅ21＝ｅ21
ｅ［１］［１］＝＋．１００００ｅ＋０１                      0ｅ22＝ｅ22
ｅ［１］［２］＝＋．１００００ｅ＋０１                      0ｅ23＝ｅ23
ｂ［１］＝＋．３００００ｅ＋０１                            0ｂ2＝ｂ2
ｅ［２］［０］＝＋．１００００ｅ＋０１                      0ｅ31＝ｅ31
ｅ［２］［１］＝＋．１００００ｅ＋０１                      0ｅ32＝ｅ32
ｅ［２］［２］＝−．１００００ｅ＋０１                      0ｅ33＝ｅ33
ｂ［２］＝＋．１００００ｅ＋０１                            0ｂ3＝ｂ3
【００５０】
ステップ２５０でカウンタｋに１をセットし、ステップ２５２を実行することによって第１導出系を見つけ、これによって、式２および３から変数ｘ1を消去する。第１導出系の係数1ｅijおよび量1ｂiは、次のようになる。
0003928921.tif 000005
【００５１】
系Ｓ1の上の第１導出系は、通常の代数形で記述した時に、次のようになる。
ａｘ1＋ｘ2＋ｘ3＝ａ＋２
（ａ−１）ｘ2＋（ａ−１）ｘ3＝２（ａ−１）
（ａ−１）ｘ2−（ａ＋１）ｘ3＝−２
【００５２】
ステップ２５０ないし２６０を繰り返すことによって、方法２００によって、次のように系Ｓ1の第２導出系が計算される。
0003928921.tif 000006
または、
ａｘ1＋ｘ2＋ｘ3＝ａ＋２
（ａ−１）ｘ2＋（ａ−１）ｘ3＝２（ａ−１）
−２ａ（ａ−１）ｘ3＝−２ａ（ａ−１）
【００５３】
後退代入のステップ２８０を実行することによって、分子ｒiおよび分母ｌiiを見つけることができる。具体的に言うと、第２導出系の最後の方程式から、分子ｒ3および分母ｌ33が、
ｌ33＝−２ａ（ａ−１）  および  ｒ3＝−２ａ（ａ−１）
になる。
【００５４】
分子ｒ3および分母ｌ33を第２方程式に代入することによって、下記が得られる。
0003928921.tif 000007
または
ｌ22＝−２ａ（１−２ａ＋ａ2）  および  ｒ2＝−２ａ（１−２ａ＋ａ2）
【００５５】
最後の後退代入で、
0003928921.tif 000008
が得られ、これによって
ｌ11＝−４ａ3（１−３ａ＋３ａ2−ａ3）  および  ｎ＝−４ａ3（１−３ａ＋３ａ2−ａ3）
が得られる。
【００５６】
同様の形で、系Ｓ2の第１導出系を、次のように記述することができる。
0003928921.tif 000009
または
ａｘ1＋２ｘ2＝ａ＋２
２（ａ−２）ｘ2＝２（ａ−２）
ａｘ2−ａｘ3＝０
【００５７】
系Ｓ2の第２導出系は次の通りである。
0003928921.tif 000010
または
ａｘ1＋２ｘ2＝ａ＋２
２（ａ−２）ｘ2＝２（ａ−２）
２ａ（２−ａ）ｘ3＝２ａ（２−ａ）
【００５８】
系Ｓ2についてやはり後退代入のステップ２８０を実行することによって、分子ｒiおよび分母ｌiiを見つけることができる。分子ｒ3および分母ｌ33は次の通りである。
ｌ33＝２ａ（２−ａ）  および  ｒ3＝２ａ（２−ａ）
【００５９】
分子ｒ3および分母ｌ33を第２方程式に代入することによって、下記が得られる。
0003928921.tif 000011
または
ｌ22＝−４ａ（４−４ａ＋ａ2）  および  ｒ2＝−４ａ（４−４ａ＋ａ2）
【００６０】
最後の後退代入で、下記が得られる
0003928921.tif 000012
または
ｌ11＝−８ａ3（８−１２ａ＋６ａ2−ａ3）  および  ｒ1＝−８ａ3（８−１２ａ＋６ａ2−ａ3）
【００６１】
ステップ２９０を実行することによって、式（ｌii）1＊（ｒi）2および（ｌii）2＊（ｒi）1が、計算され、その既約形に約される。たとえば、（ｌ22）1＊（ｒ2）2を計算することによって、下記が得られる。
0003928921.tif 000013
【００６２】
同様に、（ｌ22）2＊（ｒ2）1を計算することによって、下記が得られる。
0003928921.tif 000014
【００６３】
ステップ２９０で、同様に、ｉ＝１およびｉ＝３について式（ｌii）1＊（ｒi）2および（ｌii）2＊（ｒi）1を計算する。ステップ３００で実行される、（ｌ22）1＊（ｒ2）2と（ｌ22）2＊（ｒ2）1の単純な文字列比較によって、これらの式が一致することが示される。ｉ＝１およびｉ＝３について（ｌii）1＊（ｒi）2と（ｌii）2＊（ｒi）1の比較を繰り返し、ｉ＝１、２、および３のそれぞれについて式が一致することを見つけることによって、系Ｓ1が系Ｓ2と同値であることを示すことができる。
【００６４】
本発明の実施形態は、たとえばコンパイラ内で実施することができる。周知の通り、コンパイラは、Ｃ＋＋などの言語で記述された高水準ソース・コードから計算機実行可能オブジェクト・コードを生成する。
【００６５】
前述は、本発明の一部の実施形態だけを説明したものであり、本発明の範囲および趣旨から逸脱せずに修正または変更を加えることができ、上記の実施形態は、例示的であって制限的ではない。たとえば、３組以上の連立一次代数方程式の同値を、同値に関する組の対ごとの比較によって判定することができる。
【００６６】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００６７】
（１）連立一次代数方程式の第１組および第２組の同値を判定する、コンピュータ実施される方法であって、ｘjが未知数、ｅijが係数、ｂiが量であり、前記係数および量が既知の数式であるものとして、前記方程式のそれぞれが、
ｅi1ｘ1＋ｅi2ｘ2＋ｅi3ｘ3＋…＋ｅinｘn＝ｂi
の形であり、
ｌiiおよびｒiが代数式であり、ｋ＝｛１；２｝が、前記方程式がそこから導出された前記組の１つを示すものとして、前記方程式のそれぞれが、
（ｌii）kｘi＝（ｒi）k
の形になるまで、連立一次代数方程式の前記組のそれぞれから前記未知数を繰り返して消去するステップと、
前記未知数のそれぞれについて、積（ｌii）1＊（ｒi）2と（ｌii）2＊（ｒi）1とを比較するステップであって、前記積がすべての前記未知数について一致する場合に、連立一次代数方程式の前記第１組および前記第２組が同値である、比較するステップと
を含む、コンピュータ実施される方法。
（２）前記方法がさらに、
前記代数式を、文字列内で順次配置された１つまたは複数のトークン対の形に再計算する初期ステップであって、各前記トークン対が、オペランドが続く演算子を含む、再計算する初期ステップと、
既約式を得るために、所定の簡約化規則の組に従って前記文字列を約する初期ステップと
を含み、
前記消去するステップが、所定の動作の組に従って、前記約された文字列に対して実行される
上記（１）に記載のコンピュータ実施される方法。
（３）前記簡約化規則が、
トークン対をサブグループに配置するステップと、
配置されたサブグループのオペランド・トークンを順番に配置するステップと、
約されたサブグループを形成するために、１つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約するステップと、
約された文字列を作るために、類似するサブグループの１つまたは複数の倍数インスタンスを整理するステップと
を実行することを含む、上記（２）に記載のコンピュータ実施される方法。
（４）連立一次代数方程式の第１組および第２組の同値を判定する計算装置であって、ｘjが未知数、ｅijが係数、ｂiが量であり、前記係数および量が既知の数式であるものとして、前記方程式のそれぞれが、
ｅi1ｘ1＋ｅi2ｘ2＋ｅi3ｘ3＋…＋ｅinｘn＝ｂi
の形であり、
ｌiiおよびｒiが代数式であり、ｋ＝｛１；２｝が、前記方程式がそこから導出された前記組の１つを示すものとして、前記方程式のそれぞれが、
（ｌii）kｘi＝（ｒi）k
の形になるまで、連立一次代数方程式の前記組のそれぞれから前記未知数を繰り返して消去する手段と、
前記未知数のそれぞれについて、積（ｌii）1＊（ｒi）2と（ｌii）2＊（ｒi）1とを比較する手段であって、前記積がすべての前記未知数について一致する場合に、連立一次代数方程式の前記第１組および前記第２組が同値である、比較する手段と
を含む、計算装置。
（５）前記計算装置がさらに、
前記代数式を、文字列内で順次配置された１つまたは複数のトークン対の形に再計算する手段であって、各前記トークン対が、オペランドが続く演算子を含む、再計算する手段と、
既約式を得るために、所定の簡約化規則の組に従って前記文字列を約する手段と
を含み、
前記消去する手段が、所定の動作の組に従って、前記約された文字列に対して動作する
上記（４）に記載の計算装置。
（６）前記消去する手段が、
トークン対をサブグループに配置する所定の動作と、
配置されたサブグループのオペランド・トークンを順番に配置する所定の動作と、
約されたサブグループを形成するために、１つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約する所定の動作と、
約された文字列を作るために、類似するサブグループの１つまたは複数の倍数インスタンスを整理する所定の動作と
を実行する、上記（５）に記載の計算装置。
（７）連立一次代数方程式の第１組および第２組の同値を判定する、記憶媒体によって担持されるコンピュータ・プログラム製品であって、ｘjが未知数、ｅijが係数、ｂiが量であり、前記係数および量が既知の数式であるものとして、前記方程式のそれぞれが、
ｅi1ｘ1＋ｅi2ｘ2＋ｅi3ｘ3＋…＋ｅinｘn＝ｂi
の形であり、
ｌiiおよびｒiが代数式であり、ｋ＝｛１；２｝が、前記方程式がそこから導出された前記組の１つを示すものとして、前記方程式のそれぞれが、
（ｌii）kｘi＝（ｒi）k
の形になるまで、連立一次代数方程式の前記組のそれぞれから前記未知数を繰り返して消去するプログラム要素と、
前記未知数のそれぞれについて、積（ｌii）1＊（ｒi）2と（ｌii）2＊（ｒi）1とを比較するプログラム要素であって、前記積がすべての前記未知数について一致する場合に、連立一次代数方程式の前記第１組および前記第２組が同値である、比較するプログラム要素と
を含む、コンピュータ・プログラム製品。
（８）前記代数式を、文字列内で順次配置された１つまたは複数のトークン対の形に再計算するプログラム要素であって、各前記トークン対が、オペランドが続く演算子を含む、再計算するプログラム要素と、
既約式を得るために、所定の簡約化規則の組に従って前記文字列を約するプログラム要素と
をさらに含み、
前記消去するプログラム要素が、所定の動作の組に従って、前記約された文字列に対して動作する
上記（７）に記載のコンピュータ・プログラム製品。
（９）前記消去するプログラム要素が、
トークン対をサブグループに配置する所定の動作と、
配置されたサブグループのオペランド・トークンを順番に配置する所定の動作と、
約されたサブグループを形成するために、１つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約する所定の動作と、
約された文字列を作るために、類似するサブグループの１つまたは複数の倍数インスタンスを整理する所定の動作と
を実行する、上記（８）に記載のコンピュータ・プログラム製品。
（１０）連立一次代数方程式（ＳＬＥＡ）の組の同値を判定する、コンピュータ実施される方法であって、各前記組が、複数の代数方程式を含み、
各ＳＬＡＥを標準的な形に約すステップと、
同値が存在するかどうかを判定するためにＳＬＡＥを比較するステップと
を含む方法。
（１１）前記約するステップが、
各ＳＬＡＥを既約形に変換するステップと、
消去処理を実行するステップと、
各ＳＬＡＥの２部文字列配列形を生成する後退代入処理を実行するステップと
を含む、上記（１０）に記載の方法。
（１２）前記比較するステップが、
文字列配列の一部ともう１つの前記文字列配列の一部との積を形成するステップと、
文字列配列の他の部分と前記もう１つの文字列配列の他の部分との積を形成するステップと、
数学的同値について前記めいめいの積を比較するステップと
を含む、上記（１０）に記載の方法。
（１３）３組以上の場合に、前記比較ステップが、組の総数の対の組合せについて繰り返される、上記（１２）に記載の方法。
（１４）連立一次代数方程式（ＳＬＡＥ）の第１組および第２組の同値を判定する、コンピュータ実施される方法であって、
各ＳＬＡＥを２部分の標準的な形にするために、ＳＬＡＥの前記組のそれぞれから未知数を繰り返して消去するステップと、
一方の前記標準的な形の方程式の一部ともう１つの前記標準的な形の方程式のもう１つの部分の一部との積を形成するステップと、
前記標準的な形の方程式の他の部分と前記もう１つの標準的な形の方程式の他の部分との積を形成するステップと、
数学的同値について前記めいめいの積を比較するステップと
を含む方法。
【図面の簡単な説明】
【図１】本発明の実施形態を実践することができる、従来の汎用コンピュータ・システムの概略ブロック図である。
【図２】２組の連立一次代数方程式が同値であるかどうかを判定する方法の流れ図である。
【符号の説明】
２００  方法
２４０  すべての係数ｅijおよび量ｂiを既約形に変換するステップ
２５０  ｋ＝１をセットするステップ
２５２  第ｋ導出系を得るステップ
２５５  副系を定義するステップ
２５８  ｋを増分するステップ
２６０  ｋ＝ｎ−１かどうかを判定するステップ
２６２  線
２７０  エラー・メッセージのステップ
２８０  後退代入のステップ
２９０  式（ｌii）1＊（ｒi）2および（ｌii）2＊（ｒi）1を計算するステップ
３００  文字列比較のステップ
３１０  すべてのｉについて一致するかどうかを判定するステップ
３１２  同値を報告するステップ
３１５  非同値を報告するステップ
【図１】
0003928921.tif 000015
【図２】
0003928921.tif 000016