図面 (/)

技術 コンピュータ実施される方法、計算装置およびコンピュータ・プログラム製品

出願人 インターナショナル・ビジネス・マシーンズ・コーポレーション
発明者 ラジェンドラ・クマール・ベラ
出願日 2001年6月19日 (19年8ヶ月経過) 出願番号 2001-185339
公開日 2002年2月8日 (19年0ヶ月経過) 公開番号 2002-041496
状態 特許登録済
技術分野 複合演算
主要キーワード 変数グループ 単項演算子 数値精度 簡約化 消去段階 ガウス消去法 文字列配列 構成規則
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2002年2月8日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (3)

課題

2組の連立一次代数方程式同値を判定する、コンピュータ実施される方法(200)を提供すること。

解決手段

前記方程式のそれぞれは、ei1x1+ei2x2+ei3x3+…+eiixn=biという形であり、ここで、xjは未知数、eijは係数、biは量であり、この係数および量によって組内の未知数の間の関係が定義される。係数および量は、既知の代数式である。liiおよびriが代数式であり、k={1;2}が、その方程式がそこから導出された組の1つを示すものとして、前記方程式のそれぞれが、(lii)kxi=(ri)kの形になるまで、連立一次代数方程式の組のそれぞれから未知数を繰り返して消去する(250ないし280)。未知数のそれぞれについて、積(lii)1*(ri)2および(lii)2*(ri)1を比較する(300)。すべての未知数について積が一致する(310)場合に限って、2組の連立一次代数方程式が同値である(312)。上の方法(200)を実行する装置(100)も提供する。

概要

背景

多くの応用分野で、係数行列数値要素だけが含まれる連立一次代数方程式(SLAE、Simultaneous Linear Algebraic Equations)の1つまたは複数の系を解く必要が生じる。そのような応用分野には、工学およびシミュレーションコンピュータ・コードが含まれる。SLAEの解は、通常は、周知のガウス消去法を使用して得られる。したがって、以前の方法では、通常は、2つのそのようなSLAE系S1およびS2が解かれ、その解が比較される。しかし、そのような方法は、SLAEの一方または両方の条件が不良であるか、計算に使用される数値精度が十分に高くない場合に、必ずしも機能しない。

さらに、そのような方法は、一般に、係数行列要素が代数式であるSLAEの組、および、解が一般に代数形式であるSLAEの組を解くことに適合されていない。

概要

2組の連立一次代数方程式の同値を判定する、コンピュータ実施される方法(200)を提供すること。

前記方程式のそれぞれは、ei1x1+ei2x2+ei3x3+…+eiixn=biという形であり、ここで、xjは未知数、eijは係数、biは量であり、この係数および量によって組内の未知数の間の関係が定義される。係数および量は、既知の代数式である。liiおよびriが代数式であり、k={1;2}が、その方程式がそこから導出された組の1つを示すものとして、前記方程式のそれぞれが、(lii)kxi=(ri)kの形になるまで、連立一次代数方程式の組のそれぞれから未知数を繰り返して消去する(250ないし280)。未知数のそれぞれについて、積(lii)1*(ri)2および(lii)2*(ri)1を比較する(300)。すべての未知数について積が一致する(310)場合に限って、2組の連立一次代数方程式が同値である(312)。上の方法(200)を実行する装置(100)も提供する。

目的

本発明の目的は、2組の連立一次代数方程式が同値であるかどうかを判定する方法、装置およびコンピュータ・プログラム製品を提供することである。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

連立一次代数方程式の第1組および第2組の同値を判定する、コンピュータ実施される方法であって、xjが未知数、eijが係数、biが量であり、前記係数および量が既知の数式であるものとして、前記方程式のそれぞれが、ei1x1+ei2x2+ei3x3+…+einxn=biの形であり、liiおよびriが代数式であり、k={1;2}が、前記方程式がそこから導出された前記組の1つを示すものとして、前記方程式のそれぞれが、(lii)kxi=(ri)kの形になるまで、連立一次代数方程式の前記組のそれぞれから前記未知数を繰り返して消去するステップと、前記未知数のそれぞれについて、積(lii)1*(ri)2と(lii)2*(ri)1とを比較するステップであって、前記積がすべての前記未知数について一致する場合に、連立一次代数方程式の前記第1組および前記第2組が同値である、比較するステップとを含む、コンピュータ実施される方法。

請求項2

前記方法がさらに、前記代数式を、文字列内で順次配置された1つまたは複数のトークン対の形に再計算する初期ステップであって、各前記トークン対が、オペランドが続く演算子を含む、再計算する初期ステップと、既約式を得るために、所定の簡約化規則の組に従って前記文字列を約する初期ステップとを含み、前記消去するステップが、所定の動作の組に従って、前記約された文字列に対して実行される請求項1に記載のコンピュータ実施される方法。

請求項3

前記簡約化規則が、トークン対をサブグループに配置するステップと、配置されたサブグループのオペランド・トークン順番に配置するステップと、約されたサブグループを形成するために、1つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約するステップと、約された文字列を作るために、類似するサブグループの1つまたは複数の倍数インスタンスを整理するステップとを実行することを含む、請求項2に記載のコンピュータ実施される方法。

請求項4

連立一次代数方程式の第1組および第2組の同値を判定する計算装置であって、xjが未知数、eijが係数、biが量であり、前記係数および量が既知の数式であるものとして、前記方程式のそれぞれが、ei1x1+ei2x2+ei3x3+…+einxn=biの形であり、liiおよびriが代数式であり、k={1;2}が、前記方程式がそこから導出された前記組の1つを示すものとして、前記方程式のそれぞれが、(lii)kxi=(ri)kの形になるまで、連立一次代数方程式の前記組のそれぞれから前記未知数を繰り返して消去する手段と、前記未知数のそれぞれについて、積(lii)1*(ri)2と(lii)2*(ri)1とを比較する手段であって、前記積がすべての前記未知数について一致する場合に、連立一次代数方程式の前記第1組および前記第2組が同値である、比較する手段とを含む、計算装置。

請求項5

前記計算装置がさらに、前記代数式を、文字列内で順次配置された1つまたは複数のトークン対の形に再計算する手段であって、各前記トークン対が、オペランドが続く演算子を含む、再計算する手段と、既約式を得るために、所定の簡約化規則の組に従って前記文字列を約する手段とを含み、前記消去する手段が、所定の動作の組に従って、前記約された文字列に対して動作する請求項4に記載の計算装置。

請求項6

前記消去する手段が、トークン対をサブグループに配置する所定の動作と、配置されたサブグループのオペランド・トークンを順番に配置する所定の動作と、約されたサブグループを形成するために、1つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約する所定の動作と、約された文字列を作るために、類似するサブグループの1つまたは複数の倍数インスタンスを整理する所定の動作とを実行する、請求項5に記載の計算装置。

請求項7

連立一次代数方程式の第1組および第2組の同値を判定する、記憶媒体によって担持されるコンピュータプログラム製品であって、xjが未知数、eijが係数、biが量であり、前記係数および量が既知の数式であるものとして、前記方程式のそれぞれが、ei1x1+ei2x2+ei3x3+…+einxn=biの形であり、liiおよびriが代数式であり、k={1;2}が、前記方程式がそこから導出された前記組の1つを示すものとして、前記方程式のそれぞれが、(lii)kxi=(ri)kの形になるまで、連立一次代数方程式の前記組のそれぞれから前記未知数を繰り返して消去するプログラム要素と、前記未知数のそれぞれについて、積(lii)1*(ri)2と(lii)2*(ri)1とを比較するプログラム要素であって、前記積がすべての前記未知数について一致する場合に、連立一次代数方程式の前記第1組および前記第2組が同値である、比較するプログラム要素とを含む、コンピュータ・プログラム製品。

請求項8

前記代数式を、文字列内で順次配置された1つまたは複数のトークン対の形に再計算するプログラム要素であって、各前記トークン対が、オペランドが続く演算子を含む、再計算するプログラム要素と、既約式を得るために、所定の簡約化規則の組に従って前記文字列を約するプログラム要素とをさらに含み、前記消去するプログラム要素が、所定の動作の組に従って、前記約された文字列に対して動作する請求項7に記載のコンピュータ・プログラム製品。

請求項9

前記消去するプログラム要素が、トークン対をサブグループに配置する所定の動作と、配置されたサブグループのオペランド・トークンを順番に配置する所定の動作と、約されたサブグループを形成するために、1つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約する所定の動作と、約された文字列を作るために、類似するサブグループの1つまたは複数の倍数インスタンスを整理する所定の動作とを実行する、請求項8に記載のコンピュータ・プログラム製品。

請求項10

連立一次代数方程式(SLEA)の組の同値を判定する、コンピュータ実施される方法であって、各前記組が、複数の代数方程式を含み、各SLAE標準的な形に約すステップと、同値が存在するかどうかを判定するためにSLAEを比較するステップとを含む方法。

請求項11

前記約するステップが、各SLAEを既約形に変換するステップと、消去処理を実行するステップと、各SLAEの2部文字列配列形を生成する後退代入処理を実行するステップとを含む、請求項10に記載の方法。

請求項12

前記比較するステップが、文字列配列の一部ともう1つの前記文字列配列の一部との積を形成するステップと、文字列配列の他の部分と前記もう1つの文字列配列の他の部分との積を形成するステップと、数学的同値について前記めいめいの積を比較するステップとを含む、請求項10に記載の方法。

請求項13

3組以上の場合に、前記比較ステップが、組の総数の対の組合せについて繰り返される、請求項12に記載の方法。

請求項14

連立一次代数方程式(SLAE)の第1組および第2組の同値を判定する、コンピュータ実施される方法であって、各SLAEを2部分の標準的な形にするために、SLAEの前記組のそれぞれから未知数を繰り返して消去するステップと、一方の前記標準的な形の方程式の一部ともう1つの前記標準的な形の方程式のもう1つの部分の一部との積を形成するステップと、前記標準的な形の方程式の他の部分と前記もう1つの標準的な形の方程式の他の部分との積を形成するステップと、数学的同値について前記めいめいの積を比較するステップとを含む方法。

技術分野

(14)連立一次代数方程式(SLAE)の第1組および第2組の同値を判定する、コンピュータ実施される方法であって、各SLAEを2部分の標準的な形にするために、SLAEの前記組のそれぞれから未知数を繰り返して消去するステップと、一方の前記標準的な形の方程式の一部ともう1つの前記標準的な形の方程式のもう1つの部分の一部との積を形成するステップと、前記標準的な形の方程式の他の部分と前記もう1つの標準的な形の方程式の他の部分との積を形成するステップと、数学的同値について前記めいめいの積を比較するステップとを含む方法。

背景技術

0001

本発明は、コンピュータ実施可能な方法に関し、具体的には、2組の連立一次代数方程式が同値であるかどうかを判定する方法および装置に関する。

0002

多くの応用分野で、係数行列数値要素だけが含まれる連立一次代数方程式(SLAE、Simultaneous Linear Algebraic Equations)の1つまたは複数の系を解く必要が生じる。そのような応用分野には、工学およびシミュレーションコンピュータ・コードが含まれる。SLAEの解は、通常は、周知のガウス消去法を使用して得られる。したがって、以前の方法では、通常は、2つのそのようなSLAE系S1およびS2が解かれ、その解が比較される。しかし、そのような方法は、SLAEの一方または両方の条件が不良であるか、計算に使用される数値精度が十分に高くない場合に、必ずしも機能しない。

発明が解決しようとする課題

0003

さらに、そのような方法は、一般に、係数行列要素が代数式であるSLAEの組、および、解が一般に代数形式であるSLAEの組を解くことに適合されていない。

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

0004

本発明の目的は、2組の連立一次代数方程式が同値であるかどうかを判定する方法、装置およびコンピュータ・プログラム製品を提供することである。

0005

本発明は、組のそれぞれに複数の代数方程式が含まれる、2組の連立一次代数方程式(SLEA)の同値を判定する、コンピュータ実施される方法を提供する。この方法には、各SLAEを標準的な形に約すステップと、同値が存在するかどうかを判定するためにSLAEを比較するステップとが含まれる。

0006

本発明は、さらに、連立一次代数方程式(SLEA)の第1組と第2組の同値を判定する、コンピュータ実施される方法であって、各SLAEを2部分の標準的な形にするために、SLAEの組のそれぞれから未知数を繰り返して消去するステップと、一方の標準的な形の方程式の一部ともう1つの標準的な形の方程式の別の部分の一部との積を形成するステップと、標準的な形の方程式の他の部分ともう1つの標準的な形の方程式の他の部分との積を形成するステップと、数学的同値についてめいめいの積を比較するステップとを含む方法を提供する。

0007

さらに、連立一次代数方程式の第1組および第2組の同値を判定する、コンピュータ実施される方法であって、xjが未知数、eijが係数、biが量であるものとして、方程式のそれぞれが、
ei1x1+ei2x2+ei3x3+…+einxn=bi
の形である、コンピュータ実施される方法が提供される。係数および量は、既知の代数式である。この方法には、liiおよびriが代数式であり、k={1;2}が、その方程式がそこから導出された組の1つを示すものとして、方程式のそれぞれが、
(lii)kxi=(ri)k
の形になるまで、連立一次代数方程式の組のそれぞれから未知数を繰り返して消去するステップと、未知数のそれぞれについて、積(lii)1*(ri)2と(lii)2*(ri)1とを比較するステップであって、これらの積がすべての未知数について一致する場合に、連立一次代数方程式の第1組および第2組が同値である、比較するステップとが含まれる。

0008

本発明は、さらに、連立一次代数方程式の第1組と第2組との同値を判定する計算装置であって、xjが未知数、eijが係数、biが量であり、係数および量が既知の代数方程式であるものとして、方程式のそれぞれが、
ei1x1+ei2x2+ei3x3+…+einxn=bi
の形である、計算装置を開示する。この装置には、liiおよびriが代数式であり、k={1;2}が、その方程式がそこから導出された組の1つを示すものとして、方程式のそれぞれが、
(lii)kxi=(ri)k
の形になるまで、連立一次代数方程式の組のそれぞれから未知数を繰り返して消去する手段と、未知数のそれぞれについて、積(lii)1*(ri)2と(lii)2*(ri)1とを比較する手段であって、これらの積がすべての未知数について一致する場合に、連立一次代数方程式の第1組および第2組が同値である、比較する手段とが含まれる。

0009

本発明は、さらに、連立一次代数方程式の第1組および第2組の同値を判定する、記憶媒体によって担持されるコンピュータ・プログラム製品であって、xjが未知数、eijが係数、biが量であり、係数および量が、既知の代数式であるものとして、方程式のそれぞれが、
ei1x1+ei2x2+ei3x3+…+einxn=bi
の形である、コンピュータ・プログラム製品を開示する。このコンピュータ・プログラム製品には、liiおよびriが代数式であり、k={1;2}が、その方程式がそこから導出された組の1つを示すものとして、方程式のそれぞれが、
(lii)kxi=(ri)k
の形になるまで、連立一次代数方程式の組のそれぞれから未知数を繰り返して消去するプログラム要素と、未知数のそれぞれについて、積(lii)1*(ri)2と(lii)2*(ri)1とを比較するプログラム要素であって、これらの積がすべての未知数について一致する場合に、連立一次代数方程式の第1組および第2組が同値である、比較するプログラム要素とが含まれる。

0010

この方法には、さらに、代数式を、文字列内で順次配置された1つまたは複数のトークン対の形に再計算するステップであって、トークン対のそれぞれに、演算子とそれに続くオペランドが含まれる、再計算するステップと、既約式を得るために、所定の簡約化規則の組に従って文字列を約するステップとが含まれることが好ましい。連立一次代数方程式の組のそれぞれからの未知数の消去は、所定の動作の組に従って約された文字列に対して実行される。

0011

さらに、簡約化規則に、トークン対をサブグループに配置するステップと、配置されたサブグループのオペランド・トークン順番に配置するステップと、約されたサブグループを形成するために、1つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約するステップと、約された文字列を作るために、類似するサブグループの1つまたは複数の倍数インスタンスを整理するステップとを含めることができる。

0012

本発明の好ましい実施形態を実践することができる汎用のコンピュータ・システム100を、図1に示す。まずコンピュータ・システム100を説明し、その後、より具体的に、2組の連立一次代数方程式が同値であるかどうかを判定する方法を説明する。

0013

この方法は、コンピュータ・システム100内で実行されるアプリケーションプログラムなどのソフトウェアとして実施することができる。具体的に言うと、2組の連立一次代数方程式が同値であるかどうかを判定する方法のステップは、コンピュータ・システム100によって実行されるソフトウェア内の命令によって実施される。このソフトウェアは、たとえば下で説明する記憶装置を含む、コンピュータ可読媒体保管することができる。ソフトウェアは、コンピュータ可読媒体からコンピュータ・システム100にロードされ、その後、コンピュータ・システム100によって実行される。そのようなソフトウェアまたはコンピュータ・プログラムをその上に記録されたコンピュータ可読媒体が、コンピュータ・プログラム製品である。コンピュータでのコンピュータ・プログラム製品の使用によって、本発明の実施形態による2組の連立一次代数方程式が同値であるかどうかを判定する有利な装置がもたらされることが好ましい。

0014

コンピュータ・システム100には、コンピュータ・モジュール101と、キーボード102およびマウス103などの入力装置と、プリンタ115およびディスプレイ装置114を含む出力装置が含まれる。コンピュータ・モジュール101には、通常は、少なくとも1つのプロセッサ105と、たとえば半導体ランダムアクセスメモリ(RAM)および読取専用メモリ(ROM)から形成されるメモリ106と、ビデオインターフェース107、プリンタ115用の入出力インターフェース、およびキーボード102およびマウス103用の入出力インターフェース113を含む入出力(I/O)インターフェースとが含まれる。記憶装置109が設けられ、これには、通常は、ハードディスク110およびフロッピ・ディスク・ドライブ111が含まれる。CD−ROMドライブ(図示せず)を、データの不揮発性供給源として設けることができる。コンピュータ・モジュール101のプロセッサ105、メモリ106、ビデオ・インターフェース107、記憶装置109、ハード・ディスク110、フロッピ・ディスク・ドライブ111、および入出力インターフェース113は、通常は、相互接続されたバス104を介して、当業者に既知のコンピュータ・システム100の動作の従来のモードをもたらす形で通信する。

0015

通常、好ましい実施形他のアプリケーション・プログラムは、ハード・ディスク110に常駐し、プロセッサ105によって読み取られ、その実行の際に制御される。プログラムの中間記憶を、おそらくはハード・ディスク110と共同して、半導体メモリ106を使用して達成することができる。いくつかの場合に、アプリケーション・プログラムを、CD−ROMまたはフロッピ・ディスクにエンコードしてユーザに供給し、CD−ROMドライブ(図示せず)またはフロッピ・ディスク・ドライブ111を介して読み取ることができ、その代わりに、モデム装置(図示せず)を介してネットワーク(図示せず)からユーザが読み取ることができる。さらに、ソフトウェアは、磁気テープ、ROMまたは集積回路光磁気ディスク、コンピュータ・モジュール101と別の装置の間の無線伝送チャネルまたは赤外線伝送チャネルPCMCIAカードなどのコンピュータ可読カード電子メール送信およびウェブサイトなどに記録された情報を含むインターネットおよびイントラネットを含む他のコンピュータ可読媒体からコンピュータ・システム100にロードすることもできる。前述は、関連するコンピュータ可読媒体の例示にすぎない。他のコンピュータ可読媒体を、本発明の範囲および趣旨から逸脱せずに実践することができる。

0016

本発明のハードウェア環境を説明したので、2組の連立一次代数方程式が同値であるかどうかを判定する方法を説明する。

0017

方法の広義概要
Sが、次式によって与えられる連立一次代数方程式(SLAE)の系を表すものとする。
e11x1+e12x2+e13x3+…+e1nxn=b1
e21x1+e22x2+e23x3+…+e2nxn=b2
… … … …
en1x1+en2x2+en3x3+…+ennxn=bn
ここで、n個の未知数{x1、x2、x3、…、xn}が、n個の方程式によって関連し、係数eij(i=1、2、…、nおよびj=1、2、…、n)が、既知の代数式であり、右辺の量bi、i=1、2、…、nも代数式である。

0018

そのような2つの系S1およびS2が同値すなわち、めいめいの解が互いに同一であるかどうかを判定する方法は、おおまかに次の2つの部分を有する。
(1)下記の型の標準的な形へのSLAEの各系Sの既約化。
l11x1=r1
l22x2=r2
l33x3=r3
… …
lnnxn=rn
ここで、liiおよびriは代数式である。
(2)2組のSLAEの標準的な形での比較。

0019

SLAES1およびS2の係数eijおよび量biが、除算演算子を有しないと仮定する。望ましくない除算演算子は、影響される量に適当な係数を掛けることによって、SLAE S1およびS2から消去することができる。これは、交換可能な演算子でない除算演算子に関連するオペランドの処理の複雑さを減らすために行われる。

0020

既約式
係数および量を式として記述することができ、係数および量の項には定数および変数を含めることができる。好ましい実施形態では、2つの式の間の比較を容易にするために、下で説明するように、式の既約形という概念を使用した。既約式は、式がそれに変換される標準形である。

0021

変換される式が、構文的に正しく、空白を含まないことが、先験的に仮定される。好ましい実施形態では、変数が、その構成において、小文字英字下線文字、および数字に制限され、変数が、数字から始まってはならず、下線で終わってはならない。これらの構成規則が満たされない場合には、影響を受ける変数を、構成規則に従う代替であるが別個の変数にマッピングする(別名を割り当てる)ことができ、これらの新しい変数が、その代わりに使用される。

0022

この実施形態で採用された規則は、正整数のべきである係数eijおよび量biの変数を、変数の掛け算として書き出すことである。したがって、たとえばanは、a*a*…*aになる。ここで、aはこの積にn回現れる。

0023

所与の式を既約式に変換するために、式を、まず次の形にする。
単項演算子><オペランド><演算子><オペランド>…<演算子><オペランド>
ここで、単項演算子は、+(プラス)または−(マイナス)のいずれかであり、各演算子は、+(加算)、−(減算)、または*(乗算)の1つである。式が単項演算子から始まらない場合には、単項演算子+(プラス)を式の先頭に挿入する。たとえば
a+b*c−dは、+a+b*c−dになる。

0024

特に、括弧がないことに留意されたい。括弧が式中に存在する場合には、2つの括弧で囲まれた係数を掛ける、余分な括弧を無視するなど、括弧を除去するのに必要な演算を実行することによって括弧を除去して、所与の式を上の形にしなければならない。

0025

次に、すべての+(加算)演算子は、文字列+1*によって置換され、その結果、+が+1*になる。同様に、すべての−(減算)演算子は、文字列−1*によって置換され、その結果、−が−1*になる。したがって、たとえば+aは、+1*aになり−a*bは、−1*a*bになる。

0026

最後に、定数(前のステップで導入される1を含む)であるオペランドは、次のe形式に変換される。
”.[符号なし数]e[e符号][符号なし指数]”
ここで、[符号なし数]は、数字だけを含むn桁の数であり、nは、0より大きいプレフィックス整数である。[e符号]は、指数の符号であり、プラスの場合は>、マイナスの場合は<になる。[符号なし指数]は、数字だけを含むm桁の数であり、mは、0より大きいプレフィックスト整数である。

0027

したがって、たとえば、25=0.25*102は、.250000e>02になり、0.025=0.25*10-1は、.250000e<01になる。ここでは、n=6、m=2であると仮定する。すべての定数が、e形式では一定の長さm+n+3文字の文字列によって表されることに留意されたい。ここで、e[e符号][符号なし指数]は、10の[e符号][符号なし指数]乗を表し、実際の定数を得るためには.[符号なし数]によって表される数をかけなければならない。

0028

式には、定数である少なくとも1つのオペランドが含まれることになる。各式は、1つまたは複数の項を有し、各項は、次の形を有する。
<単項演算子><オペランド><*><オペランド>…<*><オペランド>
ここで、単項演算子は、+(プラス)または−(マイナス)であり、2つの連続するオペランドの間に、乗算演算子*がある。項を識別した後に、各定数の[e符号]を、<または>から−または+に復元する。

0029

各項では、オペランドが、そのASCII情報交換用米国標準コード)値に従って、昇順ソート再配置)される。乗算演算子が交換可能な演算子であり、したがって、オペランドの交換が完全に許容可能であるから、これは項に影響しない。定数であるオペランドは、すべてが項の先頭に集められ、その位置で、オペランドを簡単に識別でき、単一の定数によって置換することができる。したがって、たとえば、
+.100000e+01*a*b*.500000e+00
は、オペランドを昇順で配置した後に、
+.100000e+01*.500000e+00*a*b
になり、定数を整理した後に、
+.500000e+00*a*b
になる。

0030

この段階で、項は、次の形を有する。
<単項演算子><定数><*><オペランド>…<*><オペランド>
ここで、各オペランドは、変数であり、そのASCII値は、後続のオペランドがある場合に、それより小さくない。これが、項の既約形である。既約形では、項の非定数部分を変数グループと呼ぶ。たとえば、既約形の項が「+.250000e+01*a*a*b」である場合には、その変数グループは「*a*a*b」である。

0031

式では、変数グループが一致するすべての項が、項の1つの定数を変更し、同一の変数グループを有する他のすべての項を消去することによって組み合わされる。

0032

最後に、式の既約項を、そのめいめいの変数グループのASCII値に従って、昇順で再配置する。この最終形では、式が、その既約形であるという。特に、既約式のどの2つの項も、同一の変数グループを有しないことに留意されたい。

0033

同値を判定する方法
図2を参照すると、2つのそのような系S1およびS2が同値であるかどうかを判定する方法200が示されている。ステップ240から開始して、すべての係数eijおよび量biを、そのめいめいの既約形(上で説明した)に変換する。

0034

ステップ250ないし280では、ガウス消去法および後退代入法(除算をなくすように適合された)を使用して、SLAES1およびS2を標準的な形にする。

0035

ステップ250では、カウンタkに1をセットする。次のステップ252では、変数xkを、第j方程式(j=(k+1)、…、n)から消去して、第k導出系を得る。具体的に言うと、カウンタkが1に等しい状態で、変数x1を、第j方程式(j=2、3、…、n)から消去して、次のように定義される第1導出系を得る。
e11x1+e12x2+e13x3+…+e1nxn=b1
1e22x2+1e23x3+…+1e2nxn=1b2
… … … … …
1en2x2+1en3x3+…+1ennxn=1bn
ここで、第1導出系の新しい係数1ejkは、次式によって与えられる。1ejk=ejke11e1kej1 および1bj=bje11−b1ej1 ただし、(j、k)=2、…、n

0036

係数e11=0の場合には、系Sの第1方程式を、係数e1mが非ゼロの系Sの他の方程式mと交換する。そのような方程式mが見つからない場合には、SLAEが特異であり、方法200、具体的にはステップ252が、その下のステップ270への線262に従うことよって割り込まれ、ステップ270で、方法200が、適当なエラー・メッセージと共に終了する。

0037

ステップ260では、カウンタkがn−1と等しいかどうかを判定する。ここで、nは未知数の数である。そうではない場合には、ステップ255で、第k導出系から副系を定義する。たとえば、カウンタkが1に等しい場合に、第1導出系から導出される副系は、次の通りである。
1e22x2+1e23x3+…+1e2nxn=1b2
… … … … …
1en2x2+1en3x3+…+1ennxn=1bn

0038

この副系は、(n−1)個のSLAEの組であり、(n−1)個の未知数{x2、x3、…、xn}を有する。ステップ258でカウンタkを増分した後に、系Sが次のように第(n−1)導出系に約されるまで、既約化のステップ252ないし260を副系に対して繰り返す。
e11x1+e12x2+e13x3+…+e1nxn=b1
1e22x2+1e23x3+…+1e2nxn=1b2
… … … … …
n-1ennxn=n-1bn
ここで、対角係数j-1ejj (j=1、…、n)は、すべてが非ゼロであり、
1ejk=l-1ejkl-1ell−l-1elkl-1ejl
1bj=l-1bjl-1elll-1bll-1ejl ただしl=1、…、n−1; (j、k)=l+1、…、n
および
0ejk=ejk
である。

0039

これで、この処理のガウス消去段階が完了する。この処理全体に除算がないことに留意されたい。カウンタkは、現在、n−1に等しく、したがって、この方法は、ステップ280に継続し、そこで、やはり除算なしで後退代入を実行する。したがって、未知数xiを計算するのではなく、積liixiを計算する。ここで、n個の未知数xiのそれぞれが、riが分子、liiが分母である比x1=ri/liiの形で表される。i=nの場合に、次式が得られる。
n-1ennxn=n-1bn
その結果、
lnn=n-1enn および rn=n-1bn
になる。

0040

i=n−1について、第(n−1)方程式に分母lnnを掛けて、
lnnn-2en-1,n-1xn-1+lnnn-2en-1,nxn=n-2bn-1lnn
または
lnnn-2en-1,n-1xn-1=n-2bn-1lnn−n-2en-1,nrn
を得る。その結果、
ln-1,n-1=lnnn-2en-1,n-1 および rn-1=n-2bn-1lnn−n-2en-1,nrn
になる。

0041

i=n−2について、第(n−2)方程式に分母ln-1,n-1を掛け、
ln-1,n-1n-3en-2xn-2+ln-1,n-1n-3en-2,n-1xn-1+ln-1,n-1n-3en-2,nxn=n-3bn-2ln-1,n-1
または
ln-1,n-1n-3en-2,n-2xn-2=n-3bn-2ln-1,n-1−n-2en-1,n-1n-3en-2,nrn−n-3en-2,n-1rn-1
を得る。その結果、
ln-2,n-2=ln-1,n-1n-3en-2,n-2 および rn-2=n-3bn-2ln-1,n-1−n-2en-1,n-1n-3en-2,nrn−n-3en-2,n-1rn-1
になる。

0042

すべてのi=1、2、…、n−1について、結果が
lii=li+1,i+1i-1eii および ri=i-1bili+1,1+1−Rinrn−Ri,n-1rn-1−…−Ri,i+1ri+1
になり、
lnn=n-1enn および rn=n-1bn
であることを示すことができる。ここで
Rij=(li+1,i+1/ljj)i-1eij ただし、j=n、…、(i+1)、i=1、2、…、n−1
である。

0043

ljjが、li+1,i+1の因数なので、Rijが除算と無関係になることに留意されたい。しかし、後退代入のステップ280に、liiとriに共通する因数を消去するステップがないことに留意されたい。

0044

2つのSLAE系S1およびS2のそれぞれについてステップ240ないし280を完了した後に、系S1の文字列配列(lii)1および(ri)1と系S2の(lii)2および(ri)2が作られている。原則として、2つの系S1およびS2が同値であることを示すためには、それらのめいめいの文字列配列liiおよびriが一致することが示されるならば十分である。しかし、一般に、現在既知の方法によってそれらに共通する因数を完全に消去することが不可能なので、これは必ずしも可能ではない。したがって、消去されない共通の因数が存在する可能性があることを前提にしなければならない。しかし、数学的に、
(lii/ri)1=(lii/ri)2
または、これと同等であるが、
(lii)1*(ri)2=(lii)2*(ri)1
であることが明らかであり、この形で比較を実行することができる。したがって、ステップ290で、i=1、…、nのそれぞれについて、式(lii)1*(ri)2および(lii)2*(ri)1を計算する。すべての式(lii)1*(ri)2および(lii)2*(ri)1が、一貫性のある形でその既約形に約された場合には、ステップ300で、(lii)1*(ri)2と(lii)2*(ri)1の単純な文字列比較を実行する。判断ステップ310で、すべてのi=1、…、nについて一致が見つかったかどうかを判定する。回答肯定の場合には、系S1およびS2の同値を、ステップ312で報告する。そうでない場合には、ステップ315で非同値を報告する。

0045


方法200を実行して2つの系S1およびS2が同値であるかどうかを判定する例を、これから説明する。CおよびC++プログラミング言語表記を使用する。この表記では、係数および量を、それぞれe[i−1][j−1]およびb[i−1]と表記する。

0046

下に示す例を理解するために、以下の擬似コード片の参照が役に立つであろう。変数e[][]およびb[]は、なかんずくそのような式に対する演算子+(加算)、−(減算)、および*(乗算)演算子を実施する代数式データ型(datatype algebraic expression)を有する。クラスexpressionは、代数式を既約形に変換できるメソッドも有する。
//ガウス消去
// e[][]およびb[]はExpression型である。
for (i = 0; i < n-1; i++) { //導出系のインデックス
// ---コメント1 ---
// e[i][i] = 0ならば、この行を、それより下にある、
// e[i][k] != 0である別の行(たとえばk > iのk行目
// と交換する。そのようなkが見つからない場合には、
//行列eが特異であるというメッセージで終了する。
// これを行うコードはここでは示さない。
for (j = i+1; j < n; j++) {
for (k = i+1; k < n; k++) {
// i行目にe[j][i]を掛ける。
// j行目にe[i][i]を掛ける。
// i行目をj行目から引く。
e[j][k] = e[j][k]*e[i][i] - e[i][k]*e[j][i];
}
b[j] = b[j]*e[i][i] - b[i]*e[j][i];
}
// 下三角係数を0にする。
for (k = 0; k < i; k++) e[i][k] = 0;
}
//後退代入。
i = n;
// 下のwhileループの最後に、e[i-1][i-1]にliiが
// 含まれ、b[i-1]にriが含まれる。解は、
// xi = lii/riになる。
while (i--) {
j = n;
while (j--) b[j] = b[j]*e[i][i] - b[i]*e[j][i];
for(k = 0; k < n; k++) {
for (j = k; j < n; j++) {
e[k][j] *= e[i][i];
}
}
}

0047

ここで、系S1が、次の方程式の組であるものとする。
ax1+x2+x3=a+2
x1+x2+x3=3
x1+x2−x3=1
また、系S2が、次の方程式の組であるものとする。
ax1+2x2=a+2
2x1+2x2=4
x2−x3=0
すなわち、各組が3つの方程式からなる。

0048

まず系S1を検討すると、係数および量を次のように記述することができる。
e[0][0]=a
e[0][1]=1
e[0][2]=1
b[0]=a+2
e[1][0]=1
e[1][1]=1
e[1][2]=1
b[1]=3
e[2][0]=1
e[2][1]=1
e[2][2]=−1
b[2]=1

0049

系S1でステップ240を実行することによって、下記のように、係数および量のすべての項が、方法200を実行するコンピュータ・プログラムによって既約形に変換される。計算の異なる段階で擬似コード変数によって参照されるテキスト変数を、右側に示す。
既約形 変数
e[0][0]=+.10000e+01*a 0e11=e11
e[0][1]=+.10000e+01 0e12=e12
e[0][2]=+.10000e+01 0e13=e13
b[0]=+.10000e+01*a+.20000e+01 0b1=b1
e[1][0]=+.10000e+01 0e21=e21
e[1][1]=+.10000e+01 0e22=e22
e[1][2]=+.10000e+01 0e23=e23
b[1]=+.30000e+01 0b2=b2
e[2][0]=+.10000e+01 0e31=e31
e[2][1]=+.10000e+01 0e32=e32
e[2][2]=−.10000e+01 0e33=e33
b[2]=+.10000e+01 0b3=b3

0050

ステップ250でカウンタkに1をセットし、ステップ252を実行することによって第1導出系を見つけ、これによって、式2および3から変数x1を消去する。第1導出系の係数1eijおよび量1biは、次のようになる。
既約形 変数
e[0][0]=+.10000e+01*a 0e11
e[0][1]=+.10000e+01 0e12
e[0][2]=+.10000e+01 0e13
b[0]=+.10000e+01*a+.20000e+01 0b1
e[1][0]=+.00000e+00 1e2l
e[1][1]=-.10000e+01+.10000e+01*a 1e22
e[1][2]=-.10000e+01+.10000e+01*a 1e23
b[1]=-.20000e+01+.20000e+01*a 1b2
e[2][0]=+.00000e+00 1e31
e[2][1]=-.10000e+01+.10000e+01*a 1e32
e[2][2]=-.10000e+01-.10000e+01*a 1e33
b[2]=-.20000e+01 1b3

0051

系S1の上の第1導出系は、通常の代数形で記述した時に、次のようになる。
ax1+x2+x3=a+2
(a−1)x2+(a−1)x3=2(a−1)
(a−1)x2−(a+1)x3=−2

0052

ステップ250ないし260を繰り返すことによって、方法200によって、次のように系S1の第2導出系が計算される。
既約形変数
e[0][0]=+.10000e+01*a 0e11
e[0][1]=+.10000e+01 0e12
e[0][2]=+.10000e+01 0e13
b[0]=+.10000e+01*a+.20000e+01 0b1
e[1][0]=+.00000e+00 1e2l
e[1][1]=-.10000e+01+.10000e+01*a 1e22
e[1][2]=-.10000e+01+.10000e+01*a 1e23
b[1]=-.20000e+01+.20000e+01*a 1b2
e[2][0]=+.00000e+00 2e3l
e[2][1]=+.00000e+00 2e32
e[2][2]=+.20000e+01*a-.20000e+01*a*a 2e33=l33
b[2]=+2.0000e+00*a-2.0000e+00*a*a 2b3=r3
または、
ax1+x2+x3=a+2
(a−1)x2+(a−1)x3=2(a−1)
−2a(a−1)x3=−2a(a−1)

0053

後退代入のステップ280を実行することによって、分子riおよび分母liiを見つけることができる。具体的に言うと、第2導出系の最後の方程式から、分子r3および分母l33が、
l33=−2a(a−1) および r3=−2a(a−1)
になる。

0054

分子r3および分母l33を第2方程式に代入することによって、下記が得られる。
既約形変数
e[1][1]=-.20000e+01*a+.40000e+01*a*a-.20000e+01*a*a*a l22
b[1]=-.20000e+01*a+.40000e+01*a*a-.20000e+01*a*a*a r2
または
l22=−2a(1−2a+a2) および r2=−2a(1−2a+a2)

0055

最後の後退代入で、
既約形変数
e[0][0]=-.40000e+01*a*a*a+.12000e+02*a*a*a*a-.12000e+02*a*a*a*a*a+.400
00e+01*a*a*a*a*a*a l11
b[0]=-.40000e+01*a*a*a+.12000e+02*a*a*a*a-.12000e+02*a*a*a*a*a+.40000e
+01*a*a*a*a*a*a r1
が得られ、これによって
l11=−4a3(1−3a+3a2−a3) および n=−4a3(1−3a+3a2−a3)
が得られる。

0056

同様の形で、系S2の第1導出系を、次のように記述することができる。
既約形変数
e[0][0]=+.10000e+01*a 0e11
e[0][1]=+.20000e+01 0e12
e[0][2]=+.00000e+00 0e13
b[0]=+.10000e+01*a+.20000e+01 0b1
e[1][0]=+.00000e+00 1e2l
e[1][1]=-.40000e+01+.20000e+01*a 1e22
e[1][2]=+.00000e+00 1e23
b[1]=-.40000e+01+.20000e+01*a 1b2
e[2][0]=+.00000e+00 1e31
e[2][1]=+.10000e+01*a 1e32
e[2][2]=-.10000e+01*a 1e33
b[2]=+.00000e+00 1b3
または
ax1+2x2=a+2
2(a−2)x2=2(a−2)
ax2−ax3=0

0057

系S2の第2導出系は次の通りである。
既約形変数
e[0][0]=+.10000e+01*a 0e11
e[0][1]=+.20000e+01 0e12
e[0][2]=+.00000e+00 0e13
b[0]=+.10000e+01*a+.20000e+01 0b1
e[1][0]=+.00000e+00 1e2l
e[1][1]=-.40000e+01+.20000e+01*a 1e22
e[1][2]=+.00000e+00 1e23
b[1]=-.40000e+01+.20000e+01*a 1b2
e[2][0]=+.00000e+00 2e3l
e[2][1]=+.10000e+01*a 2e32
e[2][2]=+.40000e+01*a-.20000e+01*a*a 2e33=l33
b[2]=+.40000e+01*a-.20000e+01*a*a 2b3=r3
または
ax1+2x2=a+2
2(a−2)x2=2(a−2)
2a(2−a)x3=2a(2−a)

0058

系S2についてやはり後退代入のステップ280を実行することによって、分子riおよび分母liiを見つけることができる。分子r3および分母l33は次の通りである。
l33=2a(2−a) および r3=2a(2−a)

0059

分子r3および分母l33を第2方程式に代入することによって、下記が得られる。
既約形変数
e[1][1]=-.16000e+02*a+.16000e+02*a*a-.40000e+01*a*a*a l22
b[1]=-.16000e+02*a+.16000e+02*a*a-.40000e+01*a*a*a r2
または
l22=−4a(4−4a+a2) および r2=−4a(4−4a+a2)

0060

最後の後退代入で、下記が得られる
既約形変数
e[0][0]=-.64000e+02*a*a*a+.96000e+02*a*a*a*a-.48000e+02*a*a*a*a*a+.800
00e+01*a*a*a*a*a*a l11
b[0]=-.64000e+02*a*a*a+.96000e+02*a*a*a*a-.48000e+02*a*a*a*a*a+.80000e
+01*a*a*a*a*a*a r1
またはl11=−8a3(8−12a+6a2−a3) および r1=−8a3(8−12a+6a2−a3)

0061

ステップ290を実行することによって、式(lii)1*(ri)2および(lii)2*(ri)1が、計算され、その既約形に約される。たとえば、(l22)1*(r2)2を計算することによって、下記が得られる。
(l22)1*(r2)2
=(-.20000e+01*a+.40000e+01*a*a-.20000e+01*a*a*a)*
(-.16000e+02*a+.16000e+02*a*a-.40000e+01*a*a*a)
=+.32000e+02*a*a-.32000e+02*a*a*a+.80000e+01*a*a*a*a
-.64000e+02*a*a*a+.64000e+02*a*a*a*a-.16000e+02*a*a*a*a*a
+.32000e+02*a*a*a*a-.32000e+02*a*a*a*a*a+.80000e+01*a*a*a*a*a*a
=+.32000e+02*a*a-.96000e+02*a*a*a+.10400e+03*a*a*a*a
-.48000e+02*a*a*a*a*a+.80000e+01*a*a*a*a*a*a

0062

同様に、(l22)2*(r2)1を計算することによって、下記が得られる。
(l22)2*(r2)1
=(-.16000e+02*a+.16000e+02*a*a-.40000e+01*a*a*a)*
(-.20000e+01*a+.40000e+01*a*a-.20000e+01*a*a*a)
=+.32000e+02*a*a-.64000e+02*a*a*a+.32000e+02*a*a*a*a
-.32000e+02*a*a*a+.64000e+02*a*a*a*a-.32000e+02*a*a*a*a*a
+.80000e+01*a*a*a*a-.16000e+02*a*a*a*a*a+.80000e+01*a*a*a*a*a*a
=+.32000e+02*a*a-.96000e+02*a*a*a+.10400e+03*a*a*a*a
-.48000e+02*a*a*a*a*a+.80000e+01*a*a*a*a*a*a

0063

ステップ290で、同様に、i=1およびi=3について式(lii)1*(ri)2および(lii)2*(ri)1を計算する。ステップ300で実行される、(l22)1*(r2)2と(l22)2*(r2)1の単純な文字列比較によって、これらの式が一致することが示される。i=1およびi=3について(lii)1*(ri)2と(lii)2*(ri)1の比較を繰り返し、i=1、2、および3のそれぞれについて式が一致することを見つけることによって、系S1が系S2と同値であることを示すことができる。

0064

本発明の実施形態は、たとえばコンパイラ内で実施することができる。周知の通り、コンパイラは、C++などの言語で記述された高水準ソース・コードから計算機実行可能オブジェクト・コードを生成する。

0065

前述は、本発明の一部の実施形態だけを説明したものであり、本発明の範囲および趣旨から逸脱せずに修正または変更を加えることができ、上記の実施形態は、例示的であって制限的ではない。たとえば、3組以上の連立一次代数方程式の同値を、同値に関する組の対ごとの比較によって判定することができる。

0066

まとめとして、本発明の構成に関して以下の事項を開示する。

図面の簡単な説明

0067

(1)連立一次代数方程式の第1組および第2組の同値を判定する、コンピュータ実施される方法であって、xjが未知数、eijが係数、biが量であり、前記係数および量が既知の数式であるものとして、前記方程式のそれぞれが、
ei1x1+ei2x2+ei3x3+…+einxn=bi
の形であり、liiおよびriが代数式であり、k={1;2}が、前記方程式がそこから導出された前記組の1つを示すものとして、前記方程式のそれぞれが、
(lii)kxi=(ri)k
の形になるまで、連立一次代数方程式の前記組のそれぞれから前記未知数を繰り返して消去するステップと、前記未知数のそれぞれについて、積(lii)1*(ri)2と(lii)2*(ri)1とを比較するステップであって、前記積がすべての前記未知数について一致する場合に、連立一次代数方程式の前記第1組および前記第2組が同値である、比較するステップとを含む、コンピュータ実施される方法。
(2)前記方法がさらに、前記代数式を、文字列内で順次配置された1つまたは複数のトークン対の形に再計算する初期ステップであって、各前記トークン対が、オペランドが続く演算子を含む、再計算する初期ステップと、既約式を得るために、所定の簡約化規則の組に従って前記文字列を約する初期ステップとを含み、前記消去するステップが、所定の動作の組に従って、前記約された文字列に対して実行される上記(1)に記載のコンピュータ実施される方法。
(3)前記簡約化規則が、トークン対をサブグループに配置するステップと、配置されたサブグループのオペランド・トークンを順番に配置するステップと、約されたサブグループを形成するために、1つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約するステップと、約された文字列を作るために、類似するサブグループの1つまたは複数の倍数インスタンスを整理するステップとを実行することを含む、上記(2)に記載のコンピュータ実施される方法。
(4)連立一次代数方程式の第1組および第2組の同値を判定する計算装置であって、xjが未知数、eijが係数、biが量であり、前記係数および量が既知の数式であるものとして、前記方程式のそれぞれが、
ei1x1+ei2x2+ei3x3+…+einxn=bi
の形であり、liiおよびriが代数式であり、k={1;2}が、前記方程式がそこから導出された前記組の1つを示すものとして、前記方程式のそれぞれが、
(lii)kxi=(ri)k
の形になるまで、連立一次代数方程式の前記組のそれぞれから前記未知数を繰り返して消去する手段と、前記未知数のそれぞれについて、積(lii)1*(ri)2と(lii)2*(ri)1とを比較する手段であって、前記積がすべての前記未知数について一致する場合に、連立一次代数方程式の前記第1組および前記第2組が同値である、比較する手段とを含む、計算装置。
(5)前記計算装置がさらに、前記代数式を、文字列内で順次配置された1つまたは複数のトークン対の形に再計算する手段であって、各前記トークン対が、オペランドが続く演算子を含む、再計算する手段と、既約式を得るために、所定の簡約化規則の組に従って前記文字列を約する手段とを含み、前記消去する手段が、所定の動作の組に従って、前記約された文字列に対して動作する上記(4)に記載の計算装置。
(6)前記消去する手段が、トークン対をサブグループに配置する所定の動作と、配置されたサブグループのオペランド・トークンを順番に配置する所定の動作と、約されたサブグループを形成するために、1つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約する所定の動作と、約された文字列を作るために、類似するサブグループの1つまたは複数の倍数インスタンスを整理する所定の動作とを実行する、上記(5)に記載の計算装置。
(7)連立一次代数方程式の第1組および第2組の同値を判定する、記憶媒体によって担持されるコンピュータ・プログラム製品であって、xjが未知数、eijが係数、biが量であり、前記係数および量が既知の数式であるものとして、前記方程式のそれぞれが、
ei1x1+ei2x2+ei3x3+…+einxn=bi
の形であり、liiおよびriが代数式であり、k={1;2}が、前記方程式がそこから導出された前記組の1つを示すものとして、前記方程式のそれぞれが、
(lii)kxi=(ri)k
の形になるまで、連立一次代数方程式の前記組のそれぞれから前記未知数を繰り返して消去するプログラム要素と、前記未知数のそれぞれについて、積(lii)1*(ri)2と(lii)2*(ri)1とを比較するプログラム要素であって、前記積がすべての前記未知数について一致する場合に、連立一次代数方程式の前記第1組および前記第2組が同値である、比較するプログラム要素とを含む、コンピュータ・プログラム製品。
(8)前記代数式を、文字列内で順次配置された1つまたは複数のトークン対の形に再計算するプログラム要素であって、各前記トークン対が、オペランドが続く演算子を含む、再計算するプログラム要素と、既約式を得るために、所定の簡約化規則の組に従って前記文字列を約するプログラム要素とをさらに含み、前記消去するプログラム要素が、所定の動作の組に従って、前記約された文字列に対して動作する上記(7)に記載のコンピュータ・プログラム製品。
(9)前記消去するプログラム要素が、トークン対をサブグループに配置する所定の動作と、配置されたサブグループのオペランド・トークンを順番に配置する所定の動作と、約されたサブグループを形成するために、1つまたは複数の定数を整理し、反対の効果の変数を消去することによって、順序付けられたオペランドを約する所定の動作と、約された文字列を作るために、類似するサブグループの1つまたは複数の倍数インスタンスを整理する所定の動作とを実行する、上記(8)に記載のコンピュータ・プログラム製品。
(10)連立一次代数方程式(SLEA)の組の同値を判定する、コンピュータ実施される方法であって、各前記組が、複数の代数方程式を含み、各SLAEを標準的な形に約すステップと、同値が存在するかどうかを判定するためにSLAEを比較するステップとを含む方法。
(11)前記約するステップが、各SLAEを既約形に変換するステップと、消去処理を実行するステップと、各SLAEの2部文字列配列形を生成する後退代入処理を実行するステップとを含む、上記(10)に記載の方法。
(12)前記比較するステップが、文字列配列の一部ともう1つの前記文字列配列の一部との積を形成するステップと、文字列配列の他の部分と前記もう1つの文字列配列の他の部分との積を形成するステップと、数学的同値について前記めいめいの積を比較するステップとを含む、上記(10)に記載の方法。
(13)3組以上の場合に、前記比較ステップが、組の総数の対の組合せについて繰り返される、上記(12)に記載の方法。

--

0068

図1本発明の実施形態を実践することができる、従来の汎用コンピュータ・システムの概略ブロック図である。
図22組の連立一次代数方程式が同値であるかどうかを判定する方法の流れ図である。

0069

200 方法
240 すべての係数eijおよび量biを既約形に変換するステップ
250 k=1をセットするステップ
252 第k導出系を得るステップ
255 副系を定義するステップ
258 kを増分するステップ
260 k=n−1かどうかを判定するステップ
262 線
270エラー・メッセージのステップ
280後退代入のステップ
290 式(lii)1*(ri)2および(lii)2*(ri)1を計算するステップ
300文字列比較のステップ
310 すべてのiについて一致するかどうかを判定するステップ
312同値を報告するステップ
315 非同値を報告するステップ

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

該当するデータがありません

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

該当するデータがありません

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ