JPH07200538A - グレブナ基底生成方法及び装置 - Google Patents
グレブナ基底生成方法及び装置Info
- Publication number
- JPH07200538A JPH07200538A JP6255759A JP25575994A JPH07200538A JP H07200538 A JPH07200538 A JP H07200538A JP 6255759 A JP6255759 A JP 6255759A JP 25575994 A JP25575994 A JP 25575994A JP H07200538 A JPH07200538 A JP H07200538A
- Authority
- JP
- Japan
- Prior art keywords
- polynomial
- basis
- normalized
- calculation
- gröbner
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/11—Complex mathematical operations for solving equations, e.g. nonlinear equations, general mathematical optimization problems
- G06F17/12—Simultaneous equations, e.g. systems of linear equations
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Mathematical Physics (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Operations Research (AREA)
- Software Systems (AREA)
- Databases & Information Systems (AREA)
- Algebra (AREA)
- Computing Systems (AREA)
- Complex Calculations (AREA)
Abstract
(57)【要約】 （修正有）
【目的】 連立代数方程式の解法に有効なグレブナ基底
生成方法及び装置 【構成】 素数ｐを選び、多項式対の正規化形式をｐを
法として計算し、法ｐでの正規化形式が０でない場合有
理数上で正規化形式を計算し、０の場合は有理数上でも
０とみなして有理数上での正規化形式の計算を省略し、
この最終的に生成されたグレブナ基底とは限らない多項
式を含む多項式集合Ｆ1について、Ｆ1 から生成した多
項式対の正規化形式を計算することによるグレブナ基底
チェックと、Ｆの元全てがＦ1 により０に正規化される
ことを確かめることによるイデアルの同等性チェックを
行うことにより、Ｆ1 から生成したすべての多項式対の
Ｓ多項式及びＦのすべてが元がＦ1 により０に正規化さ
れる”とき、Ｆ1 がＦのグレブナ基底であることをチェ
ックし、多項式集合Ｆからグレブナ基底を生成する。
生成方法及び装置 【構成】 素数ｐを選び、多項式対の正規化形式をｐを
法として計算し、法ｐでの正規化形式が０でない場合有
理数上で正規化形式を計算し、０の場合は有理数上でも
０とみなして有理数上での正規化形式の計算を省略し、
この最終的に生成されたグレブナ基底とは限らない多項
式を含む多項式集合Ｆ1について、Ｆ1 から生成した多
項式対の正規化形式を計算することによるグレブナ基底
チェックと、Ｆの元全てがＦ1 により０に正規化される
ことを確かめることによるイデアルの同等性チェックを
行うことにより、Ｆ1 から生成したすべての多項式対の
Ｓ多項式及びＦのすべてが元がＦ1 により０に正規化さ
れる”とき、Ｆ1 がＦのグレブナ基底であることをチェ
ックし、多項式集合Ｆからグレブナ基底を生成する。
Description
【０００１】
【産業上の利用分野】本発明は、連立代数方程式などの
解法に有効なグレブナ基底の生成方法及び装置に係り、
高速演算可能でメモリ資源を節約できるグレブナ基底生
成法に関する。
解法に有効なグレブナ基底の生成方法及び装置に係り、
高速演算可能でメモリ資源を節約できるグレブナ基底生
成法に関する。
【０００２】
【従来の技術】産業・技術分野、特に工学における諸問
題において、連立代数方程式に定式化される問題は数多
い。例えば、システムの最適化問題、機械設計問題、ロ
ボットの逆運動学計算、偏微分方程式の求解など、多岐
にわたっている。しかし、これらを代数的に厳密に解く
一般的な方法は知られておらず、数値的解法に頼ること
がほとんどであった。
題において、連立代数方程式に定式化される問題は数多
い。例えば、システムの最適化問題、機械設計問題、ロ
ボットの逆運動学計算、偏微分方程式の求解など、多岐
にわたっている。しかし、これらを代数的に厳密に解く
一般的な方法は知られておらず、数値的解法に頼ること
がほとんどであった。
【０００３】近年、イデアル理論に基づく解法がいくつ
か知られるようになってきた。その一つの方法にグレブ
ナ基底を使う方法がある。この方法は、与えられた方程
式の解を、過不足なく、数値解を求めやすい形で求める
ことができるという点で優れているが、従来の方法で
は、グレブナ基底の計算自体の計算量が、時間的、空間
的にかなり大きくなる場合があるという理由で、連立方
程式の求解への実用的な応用までには至っていない。
か知られるようになってきた。その一つの方法にグレブ
ナ基底を使う方法がある。この方法は、与えられた方程
式の解を、過不足なく、数値解を求めやすい形で求める
ことができるという点で優れているが、従来の方法で
は、グレブナ基底の計算自体の計算量が、時間的、空間
的にかなり大きくなる場合があるという理由で、連立方
程式の求解への実用的な応用までには至っていない。
【０００４】グレブナ基底生成算法は、ブッフバーガー
（Buchberger）算法と呼ばれ、Buchbergerにより考案さ
れ、数多くの人々により改良され、そのアルゴリズムは
計算機に組み込まれて多くの人に使用されてきた。その
アルゴリズムの骨子は以下の通りである。
（Buchberger）算法と呼ばれ、Buchbergerにより考案さ
れ、数多くの人々により改良され、そのアルゴリズムは
計算機に組み込まれて多くの人に使用されてきた。その
アルゴリズムの骨子は以下の通りである。
【０００５】アルゴリズム（１） 入力：多項式集合Ｆ 出力：Ｆで生成されるイデアルのグレブナ基底Ｇ （１） Ｄ←｛｛ｆ，ｇ｝｜ｆ，ｇ∈Ｇ；ｆ≠ｇ｝ do｛ （２） Ｄから規準により０に正規化されることがわか
っている対を取り除く （４） Ｐ←ＣのＳ多項式 以上を簡単に説明すると、１．入力多項式集合Ｇから構
成される全ての多項式対からなる集合Ｄを作り、次項以
下を繰り返す。
っている対を取り除く （４） Ｐ←ＣのＳ多項式 以上を簡単に説明すると、１．入力多項式集合Ｇから構
成される全ての多項式対からなる集合Ｄを作り、次項以
下を繰り返す。
【０００６】２．Ｄから、ある規準により、計算するこ
となしに、０に正規化されることがわかっている元を取
り除く。 ３．Ｄが空集合ならば、Ｇを出力する。Ｄが空集合でな
ければ、Ｄから元Ｃを、ある規準により一つ取り出し、
残りを改めてＤとする。
となしに、０に正規化されることがわかっている元を取
り除く。 ３．Ｄが空集合ならば、Ｇを出力する。Ｄが空集合でな
ければ、Ｄから元Ｃを、ある規準により一つ取り出し、
残りを改めてＤとする。
【０００７】４．多項式対ＣからＳ多項式Ｐを作り、Ｇ
により正規化する。Ｐの正規化をＮＦ（Ｐ，Ｇ）と書
く。 ５．ＮＦ（Ｐ，Ｇ）が０でないならば、Ｇの各元と、Ｎ
Ｆ（Ｐ，Ｇ）からなる多項式対を全て、Ｄに加える。さ
らに、ＧにＮＦ（Ｐ，Ｇ）を加える。
により正規化する。Ｐの正規化をＮＦ（Ｐ，Ｇ）と書
く。 ５．ＮＦ（Ｐ，Ｇ）が０でないならば、Ｇの各元と、Ｎ
Ｆ（Ｐ，Ｇ）からなる多項式対を全て、Ｄに加える。さ
らに、ＧにＮＦ（Ｐ，Ｇ）を加える。
【０００８】ここで、用語の説明を行う。ここでは、多
項式を、単項式の和とみなす。単項式とは、項と係数の
積であり、項とは変数の幕積である。項の集合には、あ
る一つの全順序が定められていて、多項式ｆにあらわれ
る項の内、この順序により最大のものを頭項と呼び、Ｈ
Ｔ（ｆ）と書き、ｆにおけるＨＴ（ｆ）の係数をＨＣ
（ｆ）と書く。多項式対｛ｆ，ｇ｝のＳ多項式は、ＨＴ
（ｆ）とＨＴ（ｇ）の最小公倍項をｔとする解き、ＨＣ
（ｇ）・ｔ／ＨＴ（ｆ）・ｆ−ＨＣ（ｆ）・ｔ／ＨＴ
（ｇ）・ｇで定義される。多項式ｆが多項式ｇでリダク
ション可能とは、ＨＴ（ｇ）で割り切れるｆの項ｔが存
在する場合を言う。この場合、ｆの項ｔを、ｇにより消
去するとは、ｆにおけるｔの係数をｃとする時、ｆをｆ
−ｃ／ＨＣ（ｇ）・ｔ／ＨＴ（ｇ）・ｇに置き換えるこ
とを言う。ｆの、多項式集合Ｇによる正規化とは、ｆの
各項がＧの全ての元についてリダクション不可能になる
までＧの元によるｆの項の消去を繰り返すことを言う。
多項式集合Ｇがグレブナ基底であるとは、Ｇで生成され
るイデアルの元が全てＧにより０に正規化される場合を
言う。これは、Ｇから構成される全ての多項式対のＳ多
項式がＣにより０に正規化されることと同値である。
項式を、単項式の和とみなす。単項式とは、項と係数の
積であり、項とは変数の幕積である。項の集合には、あ
る一つの全順序が定められていて、多項式ｆにあらわれ
る項の内、この順序により最大のものを頭項と呼び、Ｈ
Ｔ（ｆ）と書き、ｆにおけるＨＴ（ｆ）の係数をＨＣ
（ｆ）と書く。多項式対｛ｆ，ｇ｝のＳ多項式は、ＨＴ
（ｆ）とＨＴ（ｇ）の最小公倍項をｔとする解き、ＨＣ
（ｇ）・ｔ／ＨＴ（ｆ）・ｆ−ＨＣ（ｆ）・ｔ／ＨＴ
（ｇ）・ｇで定義される。多項式ｆが多項式ｇでリダク
ション可能とは、ＨＴ（ｇ）で割り切れるｆの項ｔが存
在する場合を言う。この場合、ｆの項ｔを、ｇにより消
去するとは、ｆにおけるｔの係数をｃとする時、ｆをｆ
−ｃ／ＨＣ（ｇ）・ｔ／ＨＴ（ｇ）・ｇに置き換えるこ
とを言う。ｆの、多項式集合Ｇによる正規化とは、ｆの
各項がＧの全ての元についてリダクション不可能になる
までＧの元によるｆの項の消去を繰り返すことを言う。
多項式集合Ｇがグレブナ基底であるとは、Ｇで生成され
るイデアルの元が全てＧにより０に正規化される場合を
言う。これは、Ｇから構成される全ての多項式対のＳ多
項式がＣにより０に正規化されることと同値である。
【０００９】以上の計算法において、従来、行われてき
た主な改良は、 ・第２項における、０に正規化される対すなわち不必要
対の検出のための規準 ・第３項における、正規化の対象となる対の選び方の規
準 の改良の２種類に分けられる。これは、第４項における
正規化が、算法全体の計算量の主要な部分を占めること
と、第３項で取り出す対の選び方により、計算結果は常
に一意的であるにも係わらず、その後の計算経過が大き
く異なるためである。
た主な改良は、 ・第２項における、０に正規化される対すなわち不必要
対の検出のための規準 ・第３項における、正規化の対象となる対の選び方の規
準 の改良の２種類に分けられる。これは、第４項における
正規化が、算法全体の計算量の主要な部分を占めること
と、第３項で取り出す対の選び方により、計算結果は常
に一意的であるにも係わらず、その後の計算経過が大き
く異なるためである。
【００１０】前者では、現在Gebauer-Moellerによる規
準が、後者では、Giovini、Moraらによるphantom degre
eによる規準が最良とされ、実際に、有効性が確かめら
れている。
準が、後者では、Giovini、Moraらによるphantom degre
eによる規準が最良とされ、実際に、有効性が確かめら
れている。
【００１１】Gebauer,R.and Moeller,H.M.(1988). On a
n installation of Buchberger'saigorithm. J. Symb.
Comp.6/2/3,275-286.Giovini,A.et al(1991)."One suga
r cube,please," or Selection strategiesin the Buch
berger algorithm. Proc.ISSAC'91,49-54.しかし、以上
の改良によっても、第２項における不必要対を完全に排
除することはできず、残った対は実際に正規化を計算し
てはじめて、ある対が不必要対か否かを判定することが
できた。特に、問題によっては、規準によって不必要対
が除かれていても、なお、残った不必要対の正規化にか
かる時間が全体の計算時間の大部分を占めることも少な
くない。
n installation of Buchberger'saigorithm. J. Symb.
Comp.6/2/3,275-286.Giovini,A.et al(1991)."One suga
r cube,please," or Selection strategiesin the Buch
berger algorithm. Proc.ISSAC'91,49-54.しかし、以上
の改良によっても、第２項における不必要対を完全に排
除することはできず、残った対は実際に正規化を計算し
てはじめて、ある対が不必要対か否かを判定することが
できた。特に、問題によっては、規準によって不必要対
が除かれていても、なお、残った不必要対の正規化にか
かる時間が全体の計算時間の大部分を占めることも少な
くない。
【００１２】Gebauer-Moeller による規準は、極めて鋭
敏であり、これ以上不必要対を除こうとすることは、か
えって計算コストを増大させる結果となる場合がある。
このため、０に正規化される計算にかかるコストをいか
に少なくするかが、この算法の実用化の大きなポイント
の一つとなる。
敏であり、これ以上不必要対を除こうとすることは、か
えって計算コストを増大させる結果となる場合がある。
このため、０に正規化される計算にかかるコストをいか
に少なくするかが、この算法の実用化の大きなポイント
の一つとなる。
【００１３】
【発明が解決しようとする課題】正規化の計算コストが
大きくなるのは、一つの多項式の正規化において、結果
が０であるにも係わらず、任意多倍長整数である係数
が、計算途上において、しばしば極めて大きな数となっ
てしまうことによる場合が多い。この計算において、計
算機はそのような中間式を格納するためのメモリを用意
しなければならず、大容量メモリを必要とする。
大きくなるのは、一つの多項式の正規化において、結果
が０であるにも係わらず、任意多倍長整数である係数
が、計算途上において、しばしば極めて大きな数となっ
てしまうことによる場合が多い。この計算において、計
算機はそのような中間式を格納するためのメモリを用意
しなければならず、大容量メモリを必要とする。
【００１４】一般に、このような中間式膨張を避けるた
め、モジュラ演算と呼ばれる手法が用いられる場合があ
る。これは、途中の整数計算において、結果を、ある整
数すなわち法で割った剰余で置き換える方法で、当然、
中間式膨張は抑制される。ただし、真の結果に現れる整
数の大きさが、法として選んだ整数の大きさを越える場
合、モジュラ演算により得られた結果は真の結果とは一
般に異なり、真の結果を得るためには何らかの操作が必
要になる。また、得られた結果が、真の結果の係数を剰
余演算して得られるものになっている場合、その法は妥
当である、と言われるが、常に法が妥当であるという保
証はない。
め、モジュラ演算と呼ばれる手法が用いられる場合があ
る。これは、途中の整数計算において、結果を、ある整
数すなわち法で割った剰余で置き換える方法で、当然、
中間式膨張は抑制される。ただし、真の結果に現れる整
数の大きさが、法として選んだ整数の大きさを越える場
合、モジュラ演算により得られた結果は真の結果とは一
般に異なり、真の結果を得るためには何らかの操作が必
要になる。また、得られた結果が、真の結果の係数を剰
余演算して得られるものになっている場合、その法は妥
当である、と言われるが、常に法が妥当であるという保
証はない。
【００１５】グレブナ基底の計算法においても、全ての
ステップでモジュラ計算を適用し、その結果から真のグ
レブナ基底を復元するという試みがいくつかなされてい
るが、真の結果の係数の大きさが不明であり、また選ん
だ法が妥当なもとであることの確認が困難であることな
どから、算法の停止性が保証されないか、あるいは結果
の正当性の確認が困難となり、実用化されていなかっ
た。
ステップでモジュラ計算を適用し、その結果から真のグ
レブナ基底を復元するという試みがいくつかなされてい
るが、真の結果の係数の大きさが不明であり、また選ん
だ法が妥当なもとであることの確認が困難であることな
どから、算法の停止性が保証されないか、あるいは結果
の正当性の確認が困難となり、実用化されていなかっ
た。
【００１６】Winkler,F.(1988).A p-adic Approach to
the Computation of Grobner Bases. J.Synb.Comp.6/2/
3,287-304.Sasaki,T. and Takeshima,T.(1989). A Modu
lar Method for Groebner-basisConstruction over Q a
nd Solving System of Algebraic Equation. J.ofInfor
mation Processing, Vol.12, No.4, 371-379.また、論
文：Carlo Traverso（Pisa Univ.）,Groebner trace al
gorithms,Proc.ISSAC'88,Lesture Notes in Computer S
cience 358,Springer-Verlag.には、モジュラ演算によ
るグレブナ基底計算をまず行い、その際の正規化計算の
履歴を保存し，その履歴を元に、グレブナ規定を計算す
る例が記載されている。
the Computation of Grobner Bases. J.Synb.Comp.6/2/
3,287-304.Sasaki,T. and Takeshima,T.(1989). A Modu
lar Method for Groebner-basisConstruction over Q a
nd Solving System of Algebraic Equation. J.ofInfor
mation Processing, Vol.12, No.4, 371-379.また、論
文：Carlo Traverso（Pisa Univ.）,Groebner trace al
gorithms,Proc.ISSAC'88,Lesture Notes in Computer S
cience 358,Springer-Verlag.には、モジュラ演算によ
るグレブナ基底計算をまず行い、その際の正規化計算の
履歴を保存し，その履歴を元に、グレブナ規定を計算す
る例が記載されている。
【００１７】具体的には次のようになる。 １．法ｐでのグレブナ基底をまず計算する。 ２．この過程で、φ（Ｐ）を正規化する際、どの要素
で、どの項で消去したか、また、どのペアが０に正規化
したか、という履歴を保存しておく。 ３．前項の履歴を元に、有理数上でのグレブナ基底を計
算する。その際、 ・法ｐで０に正規化されたペアに関しては、有理数上の
正規化は行わない。 ・法ｐで０でない多項式に正規化されたペアに関して
は、履歴を元に有理数上で正規化する。
で、どの項で消去したか、また、どのペアが０に正規化
したか、という履歴を保存しておく。 ３．前項の履歴を元に、有理数上でのグレブナ基底を計
算する。その際、 ・法ｐで０に正規化されたペアに関しては、有理数上の
正規化は行わない。 ・法ｐで０でない多項式に正規化されたペアに関して
は、履歴を元に有理数上で正規化する。
【００１８】その際、有理数上での正規化が、法ｐでの
正規化に対応しない場合、ｐの選び方が妥当でなかった
として、ｐ をとり直して１．からやり直す。（実際に
は、やり直しの前に復活のための操作が適用される。） ４．有理数上でのグレナブ基底候補が求まったら、チェ
ックを行う。もし失敗したら、ｐをとり直して１．に戻
る。
正規化に対応しない場合、ｐの選び方が妥当でなかった
として、ｐ をとり直して１．からやり直す。（実際に
は、やり直しの前に復活のための操作が適用される。） ４．有理数上でのグレナブ基底候補が求まったら、チェ
ックを行う。もし失敗したら、ｐをとり直して１．に戻
る。
【００１９】この方法では、ｐに妥当な場合、有理数上
での正規化の際、消去すべき項を探す必要がないため、
有理数上での正規化が迅速に行われる可能性がある。一
方で、妥当でないｐを選んだ場合、それが判明するの
は、法ｐでのグレブナ基底計算を最後まで行ない、それ
を基に有理数上でのグレブナ基底計算をしている段階と
いうことになる。その判明する段階が早ければ早いほ
ど、法ｐで無駄な計算を多くしてしまい、メモリ使用量
を増大させる。
での正規化の際、消去すべき項を探す必要がないため、
有理数上での正規化が迅速に行われる可能性がある。一
方で、妥当でないｐを選んだ場合、それが判明するの
は、法ｐでのグレブナ基底計算を最後まで行ない、それ
を基に有理数上でのグレブナ基底計算をしている段階と
いうことになる。その判明する段階が早ければ早いほ
ど、法ｐで無駄な計算を多くしてしまい、メモリ使用量
を増大させる。
【００２０】本発明は、使用メモリ量を削減でき、高速
演算が可能な、グレブナ基底生成方法及び装置を提供す
ることを課題とする。
演算が可能な、グレブナ基底生成方法及び装置を提供す
ることを課題とする。
【００２１】
【課題を解決するための手段】本発明は、前記課題を解
決するために、以下のような手段を採用した。 （１）本発明は、パラメータ間の制約が連立代数方程式
で与えられるモデルにつき、該連立方程式を表すととも
にメモリ中に記述されている多項式集合Ｆからグレブナ
基底を生成するブッフバーガー演算をする計算機であ
り、素数ｐを選ぶ素数選択手段と、多項式対の正規化形
式を、ｐを法として計算する第１の演算手段と、前記法
ｐでの正規化形式が０か否かを判定する判定手段と、こ
の判定手段により前記法ｐでの正規化形式が０でないと
判定されたとき有理数上で前記正規化形式を計算する第
２の演算手段と、前記判定手段により前記法ｐでの正規
化形式が０と判断されたとき有理数上でも０とみなし
て、有理数上での正規化形式の計算を省略する省略手段
と、を有するメモリ節約制御部を備え、最終的に生成さ
れた多項式集合Ｆ1 を、グレブナ基底候補として得るこ
とのできるグレブナ基底生成装置である。
決するために、以下のような手段を採用した。 （１）本発明は、パラメータ間の制約が連立代数方程式
で与えられるモデルにつき、該連立方程式を表すととも
にメモリ中に記述されている多項式集合Ｆからグレブナ
基底を生成するブッフバーガー演算をする計算機であ
り、素数ｐを選ぶ素数選択手段と、多項式対の正規化形
式を、ｐを法として計算する第１の演算手段と、前記法
ｐでの正規化形式が０か否かを判定する判定手段と、こ
の判定手段により前記法ｐでの正規化形式が０でないと
判定されたとき有理数上で前記正規化形式を計算する第
２の演算手段と、前記判定手段により前記法ｐでの正規
化形式が０と判断されたとき有理数上でも０とみなし
て、有理数上での正規化形式の計算を省略する省略手段
と、を有するメモリ節約制御部を備え、最終的に生成さ
れた多項式集合Ｆ1 を、グレブナ基底候補として得るこ
とのできるグレブナ基底生成装置である。
【００２２】（２）ここで、さらに得られた多項式集合
Ｆ1 から生成した多項式対の正規化形式を計算すること
によるグレブナ基底チェック手段と、多項式集合Ｆの元
全てがＦ1 により０に正規化されることを確かめること
によるイデアルの同等性チェックにより、Ｆ1 がＦのグ
レブナ基底であると判定するグレブナ基底判定手段と、
このグレブナ基底判定手段による判定に失敗した場合、
前記素数選択手段による素数ｐをとり直して再度多項式
集合Ｆ1 を得る再演算制御手段と、を備えることによ
り、グレブナ基底を求めることができる。
Ｆ1 から生成した多項式対の正規化形式を計算すること
によるグレブナ基底チェック手段と、多項式集合Ｆの元
全てがＦ1 により０に正規化されることを確かめること
によるイデアルの同等性チェックにより、Ｆ1 がＦのグ
レブナ基底であると判定するグレブナ基底判定手段と、
このグレブナ基底判定手段による判定に失敗した場合、
前記素数選択手段による素数ｐをとり直して再度多項式
集合Ｆ1 を得る再演算制御手段と、を備えることによ
り、グレブナ基底を求めることができる。
【００２３】ここで、グレブナ基底判定手段は、”Ｆ1
から生成したすべての多項式対のＳ多項式及びＦのすべ
てが元がＦ1により０に正規化される”とき、Ｆ1がＦの
グレブナ基底であると判定するのである。
から生成したすべての多項式対のＳ多項式及びＦのすべ
てが元がＦ1により０に正規化される”とき、Ｆ1がＦの
グレブナ基底であると判定するのである。
【００２４】（３） 前記（１）において、第２の演算
手段（８）は、前記第１の演算手段６で得た、法ｐでの
正規化形式が０でないと判断されたとき、その都度直ち
に有理数上で前記正規化形式を計算するようにすること
が好ましい。このとき、グレブナ基底候補の頭係数を素
数ｐで割り切れるか否かを判定し、割り切れない場合の
みグレブナ基底候補の計算を続行するグレブナ基底候補
チェック手段を備えることがより好ましい。
手段（８）は、前記第１の演算手段６で得た、法ｐでの
正規化形式が０でないと判断されたとき、その都度直ち
に有理数上で前記正規化形式を計算するようにすること
が好ましい。このとき、グレブナ基底候補の頭係数を素
数ｐで割り切れるか否かを判定し、割り切れない場合の
みグレブナ基底候補の計算を続行するグレブナ基底候補
チェック手段を備えることがより好ましい。
【００２５】（４）また、対象となる多項式集合Ｆを予
め斉次化する斉次化する斉次化手段と、最終的に得られ
た多項式集合Ｆ1 を非斉次化する非斉次化手段とを備え
ることが可能である。斉次化についての詳細は後述す
る。
め斉次化する斉次化する斉次化手段と、最終的に得られ
た多項式集合Ｆ1 を非斉次化する非斉次化手段とを備え
ることが可能である。斉次化についての詳細は後述す
る。
【００２６】（５）ところで、従来の方法では、入力多
項式集合Ｆから構成される全ての多項式対からなる集合
Ｄを作ったのち、 Ｄから、ある規準により、計算することなしに、０に
正規化されることがわかっている元を取り除き、 Ｄが空集合ならば、Ｆを出力する。Ｄが空集合でなけ
れば、Ｄから元Ｃを、ある規準により一つ取り出し、残
りを改めてＤとし、 多項式対ＣからＳ多項式Ｐを作り、Ｆにより正規化
し、Ｐの正規化をＮＦ（Ｐ，Ｆ）と書き、 ＮＦ（Ｐ，Ｆ）が０でないならば、Ｆの各元と、ＮＦ
（Ｐ，Ｆ）からなる多項式対を全て、Ｄに加え、さら
に、ＦにＮＦ（Ｐ，Ｆ）を加え、これらからを繰り
返すことにより、グレブナ基底を演算していたが、本発
明では、さらに ａ）素数ｐを選び、 ｂ）多項式対の正規化形式を、ｐを法として計算し、 ｃ）法ｐでの正規化形式が０でない場合のみ有理数上で
正規化形式を計算し、 ｄ）法ｐでの正規化形式が０の場合は有理数上でも０と
みなして、有理数上での正規化形式の計算を省略し、 ｅ）グレブナ基底の候補である多項式集合Ｆ1を得るこ
とをができる。
項式集合Ｆから構成される全ての多項式対からなる集合
Ｄを作ったのち、 Ｄから、ある規準により、計算することなしに、０に
正規化されることがわかっている元を取り除き、 Ｄが空集合ならば、Ｆを出力する。Ｄが空集合でなけ
れば、Ｄから元Ｃを、ある規準により一つ取り出し、残
りを改めてＤとし、 多項式対ＣからＳ多項式Ｐを作り、Ｆにより正規化
し、Ｐの正規化をＮＦ（Ｐ，Ｆ）と書き、 ＮＦ（Ｐ，Ｆ）が０でないならば、Ｆの各元と、ＮＦ
（Ｐ，Ｆ）からなる多項式対を全て、Ｄに加え、さら
に、ＦにＮＦ（Ｐ，Ｆ）を加え、これらからを繰り
返すことにより、グレブナ基底を演算していたが、本発
明では、さらに ａ）素数ｐを選び、 ｂ）多項式対の正規化形式を、ｐを法として計算し、 ｃ）法ｐでの正規化形式が０でない場合のみ有理数上で
正規化形式を計算し、 ｄ）法ｐでの正規化形式が０の場合は有理数上でも０と
みなして、有理数上での正規化形式の計算を省略し、 ｅ）グレブナ基底の候補である多項式集合Ｆ1を得るこ
とをができる。
【００２７】さらに、このグレブナ基底とは限らない多
項式を含む多項式集合Ｆ1について、 ｅ−１）Ｆ1 から生成した多項式対の正規化形式を計算
することによるグレブナ基底チェックと、 ｅ−２）Ｆの元全てがＦ1 により０に正規化されること
を確かめることによるイデアルの同等性チェックを行う
ことにより、”Ｆ1 から生成したすべての多項式対のＳ
多項式及びＦのすべてが元がＦ1 により０に正規化され
る”とき、Ｆ1 がＦのグレブナ基底であることをチェッ
クし、 ｆ）このチェックに失敗した場合、ａ）ｐをとり直して
ｂ）からｅ）を繰り返すことでグレブナ基底を生成する
ことができる。この結果、中間式を格納するメモリの量
が少なく制御される。
項式を含む多項式集合Ｆ1について、 ｅ−１）Ｆ1 から生成した多項式対の正規化形式を計算
することによるグレブナ基底チェックと、 ｅ−２）Ｆの元全てがＦ1 により０に正規化されること
を確かめることによるイデアルの同等性チェックを行う
ことにより、”Ｆ1 から生成したすべての多項式対のＳ
多項式及びＦのすべてが元がＦ1 により０に正規化され
る”とき、Ｆ1 がＦのグレブナ基底であることをチェッ
クし、 ｆ）このチェックに失敗した場合、ａ）ｐをとり直して
ｂ）からｅ）を繰り返すことでグレブナ基底を生成する
ことができる。この結果、中間式を格納するメモリの量
が少なく制御される。
【００２８】ここで、前記（ｃ）のステップは、多項式
対の正規化形式を、ｐを法として計算し、法ｐでの正規
化形式が０でないと判断したときは、その都度直ちに有
理数上で正規化形式を計算するようにすることが好まし
い。その後、有理数上で計算された正規化形式の頭係数
を素数ｐで割り切れるか否かを判定し、割り切れない場
合のみ正規のグレブナ基底候補の計算を続行することが
好ましい。
対の正規化形式を、ｐを法として計算し、法ｐでの正規
化形式が０でないと判断したときは、その都度直ちに有
理数上で正規化形式を計算するようにすることが好まし
い。その後、有理数上で計算された正規化形式の頭係数
を素数ｐで割り切れるか否かを判定し、割り切れない場
合のみ正規のグレブナ基底候補の計算を続行することが
好ましい。
【００２９】すなわち、本発明では「多項式対の正規化
形式を、ｐを法として計算する第１の演算」Ａ１を行っ
た後、それに対応する「有理数上で前記正規化形式を計
算する第２の演算」Ｂ１を直ちに行い、Ａ１、Ｂ１、Ａ
２、Ｂ２、・・・Ａｎ、Ｂｎというように処理する。具
体的には、前記第１の演算、第２の演算により有理数上
で計算された正規化形式の頭係数を素数ｐで割り切れる
か否かを判定し、割り切れる場合は、素数を新たにとっ
て演算をやり直す。このようにすると、Ａ１、Ａ２、・
・・Ａｎ、を全て演算した後にＢ１、Ｂ２、・・・Ｂｎ
を演算する処理に比較して、演算に無駄がなく、メモリ
使用量を軽減できる。
形式を、ｐを法として計算する第１の演算」Ａ１を行っ
た後、それに対応する「有理数上で前記正規化形式を計
算する第２の演算」Ｂ１を直ちに行い、Ａ１、Ｂ１、Ａ
２、Ｂ２、・・・Ａｎ、Ｂｎというように処理する。具
体的には、前記第１の演算、第２の演算により有理数上
で計算された正規化形式の頭係数を素数ｐで割り切れる
か否かを判定し、割り切れる場合は、素数を新たにとっ
て演算をやり直す。このようにすると、Ａ１、Ａ２、・
・・Ａｎ、を全て演算した後にＢ１、Ｂ２、・・・Ｂｎ
を演算する処理に比較して、演算に無駄がなく、メモリ
使用量を軽減できる。
【００３０】すなわち、前記した論文に対し、本発明の
方法でも、法ｐで０に正規化され、かつ有理数上では正
規化されない対が存在した場合、それが判明するのはチ
ェックの段階となるが、単に、正規化された多項式の頭
係数がｐで割り切れるという場合には、ｔを計算した段
階で直ちに判明するため、残りの無駄な計算を省くこと
が出来る。
方法でも、法ｐで０に正規化され、かつ有理数上では正
規化されない対が存在した場合、それが判明するのはチ
ェックの段階となるが、単に、正規化された多項式の頭
係数がｐで割り切れるという場合には、ｔを計算した段
階で直ちに判明するため、残りの無駄な計算を省くこと
が出来る。
【００３１】さらに、対象となる多項式集合Ｆを予め斉
次化するステップと、最終的に得られた多項式集合Ｆ1
を非斉次化するステップとを備えることが可能である。
すなわち、以上の手段にいわゆる斉次化という手法を加
えることで、事実上計算不可能とされていた例について
もメモリ使用量を節約して高速にグラブナ基底を求める
ことが可能となる。
次化するステップと、最終的に得られた多項式集合Ｆ1
を非斉次化するステップとを備えることが可能である。
すなわち、以上の手段にいわゆる斉次化という手法を加
えることで、事実上計算不可能とされていた例について
もメモリ使用量を節約して高速にグラブナ基底を求める
ことが可能となる。
【００３２】斉次化自体は既知である（T.Becker and
V.Weispfenning,Groebner Bases, GTM Springer-Verla
g,1993）。斉次化は以下のように説明される。体 Ｋ
上のｎ変数多項式（x1,・・・,xn）∈Ｒ＝Ｋ［x1,・・
・,xn］に対し、ｆの、斉次化変数ｔによる斉次化（hom
ogenization）f*∈Ｒh＝Ｋ［x1,・・・,xn,t］を f*(x1,・・・,xn,t)=tdmaxf(x1/t,・・・,xn/t) （ただし、ｄmaxはｆの全次数、すなわち、ｆの各項 x1
e1・・・xn en に対し、e1+・・・+enをその項の全次数
とするとき、それらの中で最大のもの） と定義する。この操作によりｆ*は、全ての項の全次数
がｆの全次数に等しい斉次多項式となる。
V.Weispfenning,Groebner Bases, GTM Springer-Verla
g,1993）。斉次化は以下のように説明される。体 Ｋ
上のｎ変数多項式（x1,・・・,xn）∈Ｒ＝Ｋ［x1,・・
・,xn］に対し、ｆの、斉次化変数ｔによる斉次化（hom
ogenization）f*∈Ｒh＝Ｋ［x1,・・・,xn,t］を f*(x1,・・・,xn,t)=tdmaxf(x1/t,・・・,xn/t) （ただし、ｄmaxはｆの全次数、すなわち、ｆの各項 x1
e1・・・xn en に対し、e1+・・・+enをその項の全次数
とするとき、それらの中で最大のもの） と定義する。この操作によりｆ*は、全ての項の全次数
がｆの全次数に等しい斉次多項式となる。
【００３３】斉次多項式ｇ（x1,・・・,xn,t）に対し、
ｔに関する非斉次化（dehomogenization）ｇ*を、 ｇ*（x1,・・・,xn）＝ｇ（x1,・・・,xn,1） で定義する。明らかに （ｆ*）*＝ｆ が成り立つ。
ｔに関する非斉次化（dehomogenization）ｇ*を、 ｇ*（x1,・・・,xn）＝ｇ（x1,・・・,xn,1） で定義する。明らかに （ｆ*）*＝ｆ が成り立つ。
【００３４】さて、斉次多項式のみからなる多項式集合
のグレブナ基底の計算は、ブッフバーガのnormal strat
egy（正規化を行う多項式対を選ぶ際、Ｓ多項式の頭項
の順序が最も小さいものを選ぶ、という選択基準）によ
り、スムーズに計算が進行することが知られている。よ
って、入力多項式集合の各要素を斉次化し、グレブナ基
底を計算し、それを非斉次化する、という操作が考えら
れる。
のグレブナ基底の計算は、ブッフバーガのnormal strat
egy（正規化を行う多項式対を選ぶ際、Ｓ多項式の頭項
の順序が最も小さいものを選ぶ、という選択基準）によ
り、スムーズに計算が進行することが知られている。よ
って、入力多項式集合の各要素を斉次化し、グレブナ基
底を計算し、それを非斉次化する、という操作が考えら
れる。
【００３５】問題は、斉次化後のグレブナ基底と、元の
多項式集合のグレブナ基底の関係であるが、次の性質が
成り立つ。 命題 （Ｈ）ＨＴ（ｇ）*＝ＨＴ（ｇ*） 任意の斉次多項式ｇに対し（Ｈ）が成り立つならば、斉
次化後のグレブナ基底の各要素を非斉次化して得られた
多項式集合は、もとの多項式集合のグレブナ基底とな
る。
多項式集合のグレブナ基底の関係であるが、次の性質が
成り立つ。 命題 （Ｈ）ＨＴ（ｇ）*＝ＨＴ（ｇ*） 任意の斉次多項式ｇに対し（Ｈ）が成り立つならば、斉
次化後のグレブナ基底の各要素を非斉次化して得られた
多項式集合は、もとの多項式集合のグレブナ基底とな
る。
【００３６】すなわち、（Ｈ）が成り立つような項順序
を、Ｒ，Ｒhのペアに対して設定すれば良い。 １ 一般の場合 b1=a1t1s,b2=a2t2s∈Rh(a1,a2∈R) に対し、 b1>b2←→a1>a2または(a1=a2かつs1>s2) と定義する。 ２ Ｒの項順序が辞書式順序の時、Ｒhの順序を、ｔを
順序最低とする全次数辞書式順序とする。 ３ Ｒの順序が全次数逆辞書式順序の時Ｒhの順序を、
ｔを順序最低とする全次数逆辞書式順序とする。
を、Ｒ，Ｒhのペアに対して設定すれば良い。 １ 一般の場合 b1=a1t1s,b2=a2t2s∈Rh(a1,a2∈R) に対し、 b1>b2←→a1>a2または(a1=a2かつs1>s2) と定義する。 ２ Ｒの項順序が辞書式順序の時、Ｒhの順序を、ｔを
順序最低とする全次数辞書式順序とする。 ３ Ｒの順序が全次数逆辞書式順序の時Ｒhの順序を、
ｔを順序最低とする全次数逆辞書式順序とする。
【００３７】次に、本発明において利用される相互正規
化について説明する。相互正規化とは、多項式集合Ｓの
ある要素ｆを、Ｓ−｛ｆ｝で正規化する、という操作を
Ｓの各元に対して行うことである。一般にこの操作は不
定性を伴うが、Ｓがグレブナ基底となっている場合、ど
のような順序で操作を行っても結果は一定で、もとの多
項式集合と同一のイデアルのグレブナ基底となる。通
常、相互正規化を行う前に、冗長性の除去という操作を
行う。既にグレブナ基底となっているものに対しこの操
作を行っても、入力多項式集合のグレブナ基底であると
いう性質は変わらないが、本発明の場合、あくまでグレ
ブナ基底の候補である多項式集合に対し、やはりこの操
作を行っている。この理由は以下の通りである。
化について説明する。相互正規化とは、多項式集合Ｓの
ある要素ｆを、Ｓ−｛ｆ｝で正規化する、という操作を
Ｓの各元に対して行うことである。一般にこの操作は不
定性を伴うが、Ｓがグレブナ基底となっている場合、ど
のような順序で操作を行っても結果は一定で、もとの多
項式集合と同一のイデアルのグレブナ基底となる。通
常、相互正規化を行う前に、冗長性の除去という操作を
行う。既にグレブナ基底となっているものに対しこの操
作を行っても、入力多項式集合のグレブナ基底であると
いう性質は変わらないが、本発明の場合、あくまでグレ
ブナ基底の候補である多項式集合に対し、やはりこの操
作を行っている。この理由は以下の通りである。
【００３８】・冗長性除去前の候補は、確かに入力と同
一のイデアルを生成するが、それに対しグレブナ基底チ
ェックを行うことは、モジュラ演算で省いた計算をその
まま繰り返すことになり、意味がない。
一のイデアルを生成するが、それに対しグレブナ基底チ
ェックを行うことは、モジュラ演算で省いた計算をその
まま繰り返すことになり、意味がない。
【００３９】・グレブナ基底とは限らないものに対し、
冗長性除去、相互正規化を行うと、候補がグレブナ基底
でなかった場合、得られた結果の生成するイデアルが入
力イデアルと同等でなくなることも有り得るが、要素の
数が減り、しかも、順序の大きい項が減ることにより、
グレブナ基底チェックの手間が大幅に減ることが期待さ
れる。
冗長性除去、相互正規化を行うと、候補がグレブナ基底
でなかった場合、得られた結果の生成するイデアルが入
力イデアルと同等でなくなることも有り得るが、要素の
数が減り、しかも、順序の大きい項が減ることにより、
グレブナ基底チェックの手間が大幅に減ることが期待さ
れる。
【００４０】
【作用】本発明の計算機は、グレブナ基底演算のための
以下のアルゴリズムを実行する。
以下のアルゴリズムを実行する。
【００４１】＜アルゴリズム（２）＞ 入力：多項式集合Ｆ 出力：Ｆで生成されるイデアルのグレブナ基底Ｇ again： （１） ｐ←Ｆの各元の頭項の係数を割らず、かつ未使
用の素数 （２） φを、多項式ｆに対し、各係数をｐで割った剰
余に置き換えた多項式を対応させる写像とする （３） Ｄから規準により０に正規化されることがわか
っている対を取り除く （５） tp＝ＮＦ（φ（Ｐ），ＧP） （６） if tp≠0 then｛ t＝ＮＦ（Ｐ，Ｇ） （８） Ｇをグレブナ基底とみて、冗長な基底を取り除
く Ｇを相互正規化する （９）ＤO←｛｛ｆ，ｇ｝｜ｆ，ｇ∈Ｇ；ｆ≠ｇ｝ ＤOから規準により０に正規化されることがわかってい
る対を取り除くＤOの各対からＳ多項式を作り、Ｇによ
り正規化し、０でないものが出た らagainへ （１０）Ｆの各元をＧにより正規化し、０でないものが
出たらagainへ （１１）return Ｇ 本発明では、アルゴリズム（２）の第５項の如く、有理
数上の正規化形式の計算に先だって、素数ｐを法とした
正規化形式の計算を行っている。しかし、従来の方法と
異なり、この計算は、このｐを法とした正規化形式が、
０か否かを判定するためのみに用いられ、０でない場合
にはその値そのものは捨てられ、改めて、有理数上での
正規化形式が計算される。
用の素数 （２） φを、多項式ｆに対し、各係数をｐで割った剰
余に置き換えた多項式を対応させる写像とする （３） Ｄから規準により０に正規化されることがわか
っている対を取り除く （５） tp＝ＮＦ（φ（Ｐ），ＧP） （６） if tp≠0 then｛ t＝ＮＦ（Ｐ，Ｇ） （８） Ｇをグレブナ基底とみて、冗長な基底を取り除
く Ｇを相互正規化する （９）ＤO←｛｛ｆ，ｇ｝｜ｆ，ｇ∈Ｇ；ｆ≠ｇ｝ ＤOから規準により０に正規化されることがわかってい
る対を取り除くＤOの各対からＳ多項式を作り、Ｇによ
り正規化し、０でないものが出た らagainへ （１０）Ｆの各元をＧにより正規化し、０でないものが
出たらagainへ （１１）return Ｇ 本発明では、アルゴリズム（２）の第５項の如く、有理
数上の正規化形式の計算に先だって、素数ｐを法とした
正規化形式の計算を行っている。しかし、従来の方法と
異なり、この計算は、このｐを法とした正規化形式が、
０か否かを判定するためのみに用いられ、０でない場合
にはその値そのものは捨てられ、改めて、有理数上での
正規化形式が計算される。
【００４２】一方で、この値が０の場合、本来有理数上
で計算を行ってチェックすべき正規化形式の値を、０で
あるとみなして計算を省略している。原理的には、有理
数上での計算における全ての中間式に現れた係数の分
母、分子を割らない素数を選べば、必ず正しい結果が得
られることがわかっているため、停止性は保証される
が、実際にはｐとして４桁程度の素数を選んでいるた
め、妥当でないｐがどのくらいの頻度であらわれるかが
問題となる。
で計算を行ってチェックすべき正規化形式の値を、０で
あるとみなして計算を省略している。原理的には、有理
数上での計算における全ての中間式に現れた係数の分
母、分子を割らない素数を選べば、必ず正しい結果が得
られることがわかっているため、停止性は保証される
が、実際にはｐとして４桁程度の素数を選んでいるた
め、妥当でないｐがどのくらいの頻度であらわれるかが
問題となる。
【００４３】従って、本発明の有効性は、後述する終段
における結果の妥当性のチェック部分を除けば、 ・ｐを法とした正規化形式の計算を常に行うこと ・有理数上で０に正規化される計算を省略できること という二つの正負の要因の内どちらが主要な部分である
か、および、 ・有理数上の正規化形式が０でないにも係わらず、法ｐ
の計算により０と判定してしまう場合がどれくらいある
か、ということにかかっている。前者の比較は、問題に
より様々であり、一般的な議論は不可能であるが、素数
ｐを、デジタルプロセッサの提供する整数演算の範囲内
の大きさの数から選ぶことで、法ｐでの正規化計算に現
れる、整数の加減乗除をを高速化でき、問題の規模が大
きくなるほど、法ｐでの正規化計算にかかる時間は相対
的に小さくなる。また、有理数上で０に正規化される演
算の途中で、中間式膨張がひどすぎて、計算機のメモリ
容量の限界を越えることもあり得るが、結果のグレブナ
基底はそれほど大きくならない場合も多く、そのような
場合には、法ｐによる０の判定は絶大な効果を発揮す
る。
における結果の妥当性のチェック部分を除けば、 ・ｐを法とした正規化形式の計算を常に行うこと ・有理数上で０に正規化される計算を省略できること という二つの正負の要因の内どちらが主要な部分である
か、および、 ・有理数上の正規化形式が０でないにも係わらず、法ｐ
の計算により０と判定してしまう場合がどれくらいある
か、ということにかかっている。前者の比較は、問題に
より様々であり、一般的な議論は不可能であるが、素数
ｐを、デジタルプロセッサの提供する整数演算の範囲内
の大きさの数から選ぶことで、法ｐでの正規化計算に現
れる、整数の加減乗除をを高速化でき、問題の規模が大
きくなるほど、法ｐでの正規化計算にかかる時間は相対
的に小さくなる。また、有理数上で０に正規化される演
算の途中で、中間式膨張がひどすぎて、計算機のメモリ
容量の限界を越えることもあり得るが、結果のグレブナ
基底はそれほど大きくならない場合も多く、そのような
場合には、法ｐによる０の判定は絶大な効果を発揮す
る。
【００４４】また、後者、すなわち、有理数上の正規化
形式が０でないにも係わらず、法ｐの計算により０と判
定してしまう場合がどれくらいあるか、という点に関し
ては、あくまで実験による推測の域を出ないが、グレブ
ナ基底計算の著名なテスト問題を試してみた結果、４桁
程度の大きさの素数を用いればほとんど全ての問題にお
いて、一回の試行で正しい結果が得られることがわかっ
ている。
形式が０でないにも係わらず、法ｐの計算により０と判
定してしまう場合がどれくらいあるか、という点に関し
ては、あくまで実験による推測の域を出ないが、グレブ
ナ基底計算の著名なテスト問題を試してみた結果、４桁
程度の大きさの素数を用いればほとんど全ての問題にお
いて、一回の試行で正しい結果が得られることがわかっ
ている。
【００４５】この根拠として、以下のことが考えられ
る。この算法では、有理数で計算された正規化形式の頭
係数が法ｐで０でないことが要請されている。このこと
が「有理数上の正規化形式が０でないにもかかわらず、
法ｐで０になるならば、有理数上の正規化形式の係数が
全てｐで割り切れること」を保証する。よって、ｐが大
きければ、有理数上の正規化形式の係数が全てｐで割り
切れる確立は極めて小さいものであると期待されるので
ある。
る。この算法では、有理数で計算された正規化形式の頭
係数が法ｐで０でないことが要請されている。このこと
が「有理数上の正規化形式が０でないにもかかわらず、
法ｐで０になるならば、有理数上の正規化形式の係数が
全てｐで割り切れること」を保証する。よって、ｐが大
きければ、有理数上の正規化形式の係数が全てｐで割り
切れる確立は極めて小さいものであると期待されるので
ある。
【００４６】次に、終段における結果の妥当性のチェッ
クについて述べる。このチェックは １．グレブナ基底であることのチェック（アルゴリズム
（１）の第１０項） ２．入力イデアルと出力イデアルの同等性のチェック
（アルゴリズム（１）の第１１項） の２段階からなる。前者は、得られた多項式集合Ｇを、
改めて、アルゴリズム（２）に示される通常のグレブナ
基底計算算法にかけることにより行われる。ここで、も
し、Ｇがグレブナ基底になっていれば、Ｇから構成され
た多項式対は全てＧにより０に正規化される。
クについて述べる。このチェックは １．グレブナ基底であることのチェック（アルゴリズム
（１）の第１０項） ２．入力イデアルと出力イデアルの同等性のチェック
（アルゴリズム（１）の第１１項） の２段階からなる。前者は、得られた多項式集合Ｇを、
改めて、アルゴリズム（２）に示される通常のグレブナ
基底計算算法にかけることにより行われる。ここで、も
し、Ｇがグレブナ基底になっていれば、Ｇから構成され
た多項式対は全てＧにより０に正規化される。
【００４７】しかし、この計算は全て有理数上で行われ
るため、もし、前段で省略した有理数上での正規化をこ
こで行うことになれば、モジュラ計算による効果は解消
されることになる。しかし、実際には、第８項で、冗長
性を除いているため、実際に正規化すべき多項式対は、
前段における多項式対の数と比べて少なくなっており、
かつ相互正規化も行っているため、一つの多項式対を正
規化する手間も少なくてすむ。
るため、もし、前段で省略した有理数上での正規化をこ
こで行うことになれば、モジュラ計算による効果は解消
されることになる。しかし、実際には、第８項で、冗長
性を除いているため、実際に正規化すべき多項式対は、
前段における多項式対の数と比べて少なくなっており、
かつ相互正規化も行っているため、一つの多項式対を正
規化する手間も少なくてすむ。
【００４８】さらに、後者のイデアルの同等性のチェッ
クであるが、この時点でＧは、第９項により、グレブナ
基底であることは示されており、かつ構成法から入力多
項式集合Ｆで生成されるイデアルの部分イデアルになっ
ている。故に、入力多項式集合の各元が、Ｇにより０に
正規化されることが、イデアルの同等性の必要十分条件
となる。このチェックも、有理数上での正規化計算であ
るが、一般に、Ｆはそれほど大きくない場合である場合
が多く、このチェックにかかる時間も、それまで既に行
われた計算にかかる時間に比べて小さい割合である場合
が多い。
クであるが、この時点でＧは、第９項により、グレブナ
基底であることは示されており、かつ構成法から入力多
項式集合Ｆで生成されるイデアルの部分イデアルになっ
ている。故に、入力多項式集合の各元が、Ｇにより０に
正規化されることが、イデアルの同等性の必要十分条件
となる。このチェックも、有理数上での正規化計算であ
るが、一般に、Ｆはそれほど大きくない場合である場合
が多く、このチェックにかかる時間も、それまで既に行
われた計算にかかる時間に比べて小さい割合である場合
が多い。
【００４９】以上の結果、中間式を確保するメモリの大
きさを小さくできる。以上の手段にいわゆる斉次化とい
う手法を加える場合について説明する。斉次化とは、方
程式の各項の次数を同一にすることである。例えば、ｆ
（ｘ、ｙ）＝２ｘ2ｙ＋ｘｙ＋ｘ＋１という方程式があ
るとする。この各項の次数をみると、２ｘ2ｙにおい
て、２の次数は０、ｘ2の次数は２、ｙの次数は１であ
るから２ｘ2ｙの次数は２＋１＝３である。同様に、ｘ
ｙの次数は２、ｘの次数は１、１の次数は０である。
きさを小さくできる。以上の手段にいわゆる斉次化とい
う手法を加える場合について説明する。斉次化とは、方
程式の各項の次数を同一にすることである。例えば、ｆ
（ｘ、ｙ）＝２ｘ2ｙ＋ｘｙ＋ｘ＋１という方程式があ
るとする。この各項の次数をみると、２ｘ2ｙにおい
て、２の次数は０、ｘ2の次数は２、ｙの次数は１であ
るから２ｘ2ｙの次数は２＋１＝３である。同様に、ｘ
ｙの次数は２、ｘの次数は１、１の次数は０である。
【００５０】この方程式の項の各次数を同一にするた
め、新しい変数ｔを導入する。ｆ（ｘ、ｙ、ｔ）＝２ｘ
2ｙ＋ｘｙｔ＋ｘｔ2＋１ｔ3 とすれば、各項の次数はす
べて３となる。
め、新しい変数ｔを導入する。ｆ（ｘ、ｙ、ｔ）＝２ｘ
2ｙ＋ｘｙｔ＋ｘｔ2＋１ｔ3 とすれば、各項の次数はす
べて３となる。
【００５１】このように次数を同一にした後に本発明に
おけるグレブナ基底を求め、得られた解においてｔ＝１
を代入すれば、次数は元に戻る。一般に、グレブナ基底
計算は、計算途中で選んでくる多項式対の選び方によ
り、計算効率が大きく影響され、それだけメモリ使用量
が多くなる。多項式対の選び方が不適当な場合、０でな
い正規化の計算にかかる時間が増大し、最悪の場合には
メモリが満杯となって計算不能となる。そこで、斉次化
されたものをグレブナ基底計算の対象とすれば、標準的
な多項式対の選び方により、最大の計算効率を達成でき
る。
おけるグレブナ基底を求め、得られた解においてｔ＝１
を代入すれば、次数は元に戻る。一般に、グレブナ基底
計算は、計算途中で選んでくる多項式対の選び方によ
り、計算効率が大きく影響され、それだけメモリ使用量
が多くなる。多項式対の選び方が不適当な場合、０でな
い正規化の計算にかかる時間が増大し、最悪の場合には
メモリが満杯となって計算不能となる。そこで、斉次化
されたものをグレブナ基底計算の対象とすれば、標準的
な多項式対の選び方により、最大の計算効率を達成でき
る。
【００５２】しかし、斉次化の欠点として、斉次化によ
り不必要対が急速に増えるという問題がある。特に斉次
化によって、現れる不必要対の正規化は、後になって残
っているものほど長大な整数の演算が必要とされるもの
が多く、斉次化によって得られた効果を打ち消してしま
う場合も少なくない。
り不必要対が急速に増えるという問題がある。特に斉次
化によって、現れる不必要対の正規化は、後になって残
っているものほど長大な整数の演算が必要とされるもの
が多く、斉次化によって得られた効果を打ち消してしま
う場合も少なくない。
【００５３】そこで、本発明では、斉次化を利用しつ
つ、斉次化の欠点を解消し、メモリの利用効率を高めた
グレブナ基底の生成方法、装置を提供する。斉次化を用
いたグレブナ基底の計算は通常の場合、次のように行わ
れる。
つ、斉次化の欠点を解消し、メモリの利用効率を高めた
グレブナ基底の生成方法、装置を提供する。斉次化を用
いたグレブナ基底の計算は通常の場合、次のように行わ
れる。
【００５４】まず、入力多項式集合Ｆの各多項式を前記
のように斉次化した多項式集合Ｆhを作る。次に、Ｆh
のグレブナ基底Ｇh を計算する。そして、このＧh を非
斉次化し、必要があれば相互正規化を行ったものをＧと
する。このＧがＦのグレブナ基底となる。
のように斉次化した多項式集合Ｆhを作る。次に、Ｆh
のグレブナ基底Ｇh を計算する。そして、このＧh を非
斉次化し、必要があれば相互正規化を行ったものをＧと
する。このＧがＦのグレブナ基底となる。
【００５５】ここで、Ｆh のグレブナ基底の計算に用い
られる項順序は、Ｆに対する項順序から決定することが
できる。先に述べたようにグレブナ基底計算において発
生する不必要対が全体の計算効率、ひいてはメモリ使用
効率に悪影響を及ぼすが、このグレブナ基底計算に本発
明のモジュラ演算を適用することにより、不必要対の増
加による計算時間の増大すなわちメモリの使用量が押さ
えられる。しかし、上記でＦh のグレブナ基底そのもの
を計算しようとした場合、Ｆh の斉次化により、一般に
冗長性の除去操作を行ってもＧh の基底の個数は非常に
大きいものとなり、また「不必要対の選択基準」に従っ
た不必要対の除去を行ってももあまり効果がないため、
モジュラ演算法の後半部分のグレブナ基底チェックの
際、モジュラ演算により省略した不必要対の正規化を殆
どすべて行わなければならない。
られる項順序は、Ｆに対する項順序から決定することが
できる。先に述べたようにグレブナ基底計算において発
生する不必要対が全体の計算効率、ひいてはメモリ使用
効率に悪影響を及ぼすが、このグレブナ基底計算に本発
明のモジュラ演算を適用することにより、不必要対の増
加による計算時間の増大すなわちメモリの使用量が押さ
えられる。しかし、上記でＦh のグレブナ基底そのもの
を計算しようとした場合、Ｆh の斉次化により、一般に
冗長性の除去操作を行ってもＧh の基底の個数は非常に
大きいものとなり、また「不必要対の選択基準」に従っ
た不必要対の除去を行ってももあまり効果がないため、
モジュラ演算法の後半部分のグレブナ基底チェックの
際、モジュラ演算により省略した不必要対の正規化を殆
どすべて行わなければならない。
【００５６】しかし、以下の方法によれば、このような
問題を回避して斉次化とモジュラ演算の効果を最大限に
生かし、メモリの使用を最小限として、資源の有効活用
を図ることができる。
問題を回避して斉次化とモジュラ演算の効果を最大限に
生かし、メモリの使用を最小限として、資源の有効活用
を図ることができる。
【００５７】斉次化＋モジュラ演算法１．入力多項式集
合Ｆの各多項式を斉次化した多項式集合集合Ｆh を作
る。２．新たに素数ｐを選び、Ｆh のグレブナ基底候補
Ｇ'hをモジュラ演算法により計算する。
合Ｆの各多項式を斉次化した多項式集合集合Ｆh を作
る。２．新たに素数ｐを選び、Ｆh のグレブナ基底候補
Ｇ'hをモジュラ演算法により計算する。
【００５８】すなわち、入力多項式集合Ｆから構成され
る全ての多項式対からなる集合Ｄを作ったのち、 Ｄから、ある規準により、計算することなしに、０に
正規化されることがわかっている元を取り除き、 Ｄが空集合ならば、Ｆを出力する。Ｄが空集合でなけ
れば、Ｄから元Ｃを、ある規準により一つ取り出し、残
りを改めてＤとし、 多項式対ＣからＳ多項式Ｐを作り、Ｆにより正規化
し、Ｐの正規化をＮＦ（Ｐ，Ｆ）と書き、 ＮＦ（Ｐ，Ｆ）が０でないならば、Ｆの各元と、ＮＦ
（Ｐ，Ｆ）からなる多項式対を全て、Ｄに加え、さら
に、ＦにＮＦ（Ｐ，Ｆ）を加え、これらからを繰り
返すことにより、」パラメータ間の制約が連立代数方程
式で与えられるモデルについて、該連立方程式を表す、
メモリ中に記述されている多項式集合Ｆからグレブナ基
底を生成するブッフバーガー演算をする計算機におい
て、 ａ）素数ｐを選び、 ｂ）多項式対の正規化形式を、ｐを法として計算し、 ｃ）法ｐでの正規化形式が０でない場合のみ有理数上で
正規化形式を計算し、 ｄ）法ｐでの正規化形式が０の場合は有理数上でも０と
みなして、有理数上での正規化形式の計算を省略し、 ｅ）グレブナ基底の候補Ｇ'hである多項式集合Ｆ1 を得
る。 ３．そして、Ｇ'hを非斉次化し、相互正規化を行ったも
のをＧ’とする。 ４．Ｇ’に対しグレブナ基底チェックを行う。 ５．もし、チェックを通れば、Ｇ’がＦのグレブナ基
底、もし通らなければ、前記２に戻り、再度素数ｐを選
ぶ操作をし、その後前記の操作を繰り返す。
る全ての多項式対からなる集合Ｄを作ったのち、 Ｄから、ある規準により、計算することなしに、０に
正規化されることがわかっている元を取り除き、 Ｄが空集合ならば、Ｆを出力する。Ｄが空集合でなけ
れば、Ｄから元Ｃを、ある規準により一つ取り出し、残
りを改めてＤとし、 多項式対ＣからＳ多項式Ｐを作り、Ｆにより正規化
し、Ｐの正規化をＮＦ（Ｐ，Ｆ）と書き、 ＮＦ（Ｐ，Ｆ）が０でないならば、Ｆの各元と、ＮＦ
（Ｐ，Ｆ）からなる多項式対を全て、Ｄに加え、さら
に、ＦにＮＦ（Ｐ，Ｆ）を加え、これらからを繰り
返すことにより、」パラメータ間の制約が連立代数方程
式で与えられるモデルについて、該連立方程式を表す、
メモリ中に記述されている多項式集合Ｆからグレブナ基
底を生成するブッフバーガー演算をする計算機におい
て、 ａ）素数ｐを選び、 ｂ）多項式対の正規化形式を、ｐを法として計算し、 ｃ）法ｐでの正規化形式が０でない場合のみ有理数上で
正規化形式を計算し、 ｄ）法ｐでの正規化形式が０の場合は有理数上でも０と
みなして、有理数上での正規化形式の計算を省略し、 ｅ）グレブナ基底の候補Ｇ'hである多項式集合Ｆ1 を得
る。 ３．そして、Ｇ'hを非斉次化し、相互正規化を行ったも
のをＧ’とする。 ４．Ｇ’に対しグレブナ基底チェックを行う。 ５．もし、チェックを通れば、Ｇ’がＦのグレブナ基
底、もし通らなければ、前記２に戻り、再度素数ｐを選
ぶ操作をし、その後前記の操作を繰り返す。
【００５９】ここでは、モジュラ演算法によるグレブナ
基底候補生成と、グレブナ基底チェックとの間に非斉次
化を行ったことに特徴を有する。斉次化Ｆh のグレブナ
基底候補であるＧ'hは基底の個数も大きく、またＧ'hに
対するグレブナ基底チェックは、数多くの正規化計算を
行わなければならない。しかし、最終的に求めたいもの
はＦのグレブナ基底であり、Ｆh のグレブナ基底を求め
る必要はないため、Ｇ'h のグレブナ基底チェックを省
き、Ｇ'hの非斉次化から直接Ｆのグレブナ基底候補を求
めるのである。Ｇ'hの非斉次化は次の効果をもたらす。 １．Ｇ'hを非斉次化した段階で多くの基底が冗長とな
り、それらの冗長基底は除かれ、Ｇ' はＧ'hに比べてか
なり要素の個数が減る。 ２．Ｇ' は非斉次化されているため、グレブナ基底チェ
ックにおいて必要となる不必要対の正規化は、Ｇ'hにお
ける場合に比べて大きく減少することが期待される。以
上により、＜斉次化＋モジュラ演算＞は正規化対の不適
当な選択により計算できなくなるような例に対しても、
安定して高速にグレブナ基底を生成することを可能にす
る。
基底候補生成と、グレブナ基底チェックとの間に非斉次
化を行ったことに特徴を有する。斉次化Ｆh のグレブナ
基底候補であるＧ'hは基底の個数も大きく、またＧ'hに
対するグレブナ基底チェックは、数多くの正規化計算を
行わなければならない。しかし、最終的に求めたいもの
はＦのグレブナ基底であり、Ｆh のグレブナ基底を求め
る必要はないため、Ｇ'h のグレブナ基底チェックを省
き、Ｇ'hの非斉次化から直接Ｆのグレブナ基底候補を求
めるのである。Ｇ'hの非斉次化は次の効果をもたらす。 １．Ｇ'hを非斉次化した段階で多くの基底が冗長とな
り、それらの冗長基底は除かれ、Ｇ' はＧ'hに比べてか
なり要素の個数が減る。 ２．Ｇ' は非斉次化されているため、グレブナ基底チェ
ックにおいて必要となる不必要対の正規化は、Ｇ'hにお
ける場合に比べて大きく減少することが期待される。以
上により、＜斉次化＋モジュラ演算＞は正規化対の不適
当な選択により計算できなくなるような例に対しても、
安定して高速にグレブナ基底を生成することを可能にす
る。
【００６０】本発明は、システムの最適化問題、機械設
計問題、ロボットの逆運動学計算、偏微分方程式の求解
などの他、ＣＡＤやコンピュータグラフィックスにおけ
る３次元モデル作成に際して、物体と物体とを滑らかに
つなぐ、いわゆるブレンディング面の生成に利用でき
る。
計問題、ロボットの逆運動学計算、偏微分方程式の求解
などの他、ＣＡＤやコンピュータグラフィックスにおけ
る３次元モデル作成に際して、物体と物体とを滑らかに
つなぐ、いわゆるブレンディング面の生成に利用でき
る。
【００６１】
【実施例】以下、本発明の実施例を説明する。
【００６２】＜実施例１＞図１に示したように、本発明
に係る計算機は、多項式を入力する多項式入力部１と、
この入力された多項式について、演算をする演算部２
と、演算部による中間的演算結果や最終結果等を記憶す
るメモリ３と、メモリの容量を制御するメモリ節約部４
とを有する。なお、演算部とメモリ節約部とは、前記ア
ルゴリズム２を実行するプログラムによりコンピュータ
の中央演算装置上に実現される一体的なものであり、物
理的に存在するものではない。よって、この中央演算装
置上に、素数ｐを選ぶ素数選択手段５と、多項式対の正
規化形式を、ｐを法として計算する第１の演算手段６
と、前記法ｐでの正規化形式が０か否かを判定する判定
手段７と、この判定手段により前記法ｐでの正規化形式
が０でないと判定されたとき有理数上で前記正規化形式
を計算する第２の演算手段８と、グレブナ基底候補の頭
係数を素数ｐで割り切れるか否かを判定し、割り切れな
い場合のみグレブナ基底候補の計算を続行するグレブナ
基底候補チェック手段１０と、前記判定手段により前記
法ｐでの正規化形式が０と判断されたとき有理数上でも
０とみなして、有理数上での正規化形式の計算を省略す
る省略手段９と、得られた多項式集合Ｆ1 から生成した
多項式対の正規化形式を計算することによるグレブナ基
底チェック手段２０と、多項式集合Ｆの元全てがＦ1に
より０に正規化されることを確かめることによるイデア
ルの同等性チェックにより、”Ｆ1から生成したすべて
の多項式対のＳ多項式及びＦのすべてが元がＦ1により
０に正規化される”とき、Ｆ1がＦのグレブナ基底であ
ると判定するグレブナ基底判定手段２１と、このグレブ
ナ基底判定手段による判定に失敗した場合、前記素数選
択手段による素数ｐをとり直して再度多項式集合Ｆ1を
得る再演算制御手段２２とが実現されるのである。
に係る計算機は、多項式を入力する多項式入力部１と、
この入力された多項式について、演算をする演算部２
と、演算部による中間的演算結果や最終結果等を記憶す
るメモリ３と、メモリの容量を制御するメモリ節約部４
とを有する。なお、演算部とメモリ節約部とは、前記ア
ルゴリズム２を実行するプログラムによりコンピュータ
の中央演算装置上に実現される一体的なものであり、物
理的に存在するものではない。よって、この中央演算装
置上に、素数ｐを選ぶ素数選択手段５と、多項式対の正
規化形式を、ｐを法として計算する第１の演算手段６
と、前記法ｐでの正規化形式が０か否かを判定する判定
手段７と、この判定手段により前記法ｐでの正規化形式
が０でないと判定されたとき有理数上で前記正規化形式
を計算する第２の演算手段８と、グレブナ基底候補の頭
係数を素数ｐで割り切れるか否かを判定し、割り切れな
い場合のみグレブナ基底候補の計算を続行するグレブナ
基底候補チェック手段１０と、前記判定手段により前記
法ｐでの正規化形式が０と判断されたとき有理数上でも
０とみなして、有理数上での正規化形式の計算を省略す
る省略手段９と、得られた多項式集合Ｆ1 から生成した
多項式対の正規化形式を計算することによるグレブナ基
底チェック手段２０と、多項式集合Ｆの元全てがＦ1に
より０に正規化されることを確かめることによるイデア
ルの同等性チェックにより、”Ｆ1から生成したすべて
の多項式対のＳ多項式及びＦのすべてが元がＦ1により
０に正規化される”とき、Ｆ1がＦのグレブナ基底であ
ると判定するグレブナ基底判定手段２１と、このグレブ
ナ基底判定手段による判定に失敗した場合、前記素数選
択手段による素数ｐをとり直して再度多項式集合Ｆ1を
得る再演算制御手段２２とが実現されるのである。
【００６３】なお、メモリには、図２から図７に示した
ように、各種データ構造が構築される。このメモリへの
格納量が少なくてすめば、メモリ自体のハード的な容量
が少なくてすみ、また、演算速度も速くなる。
ように、各種データ構造が構築される。このメモリへの
格納量が少なくてすめば、メモリ自体のハード的な容量
が少なくてすみ、また、演算速度も速くなる。
【００６４】図２から図７において、四角で示した構造
はメモリ上の連続領域、すなわち配列を表す。ａ1→Ｒ
はａ1が領域Ｒの先頭を指すポインタであることを示
す。図２は自然数を表す。図３は有理数を表す。図４は
項を表す。図５は多項式を表す。図６、図７は集合Ｓ＝
｛ａ1、・・・ａm｝のメモリ上での表現である。集合は
計算機上ではリスト、配列において順序を無視したもの
として表現できる。
はメモリ上の連続領域、すなわち配列を表す。ａ1→Ｒ
はａ1が領域Ｒの先頭を指すポインタであることを示
す。図２は自然数を表す。図３は有理数を表す。図４は
項を表す。図５は多項式を表す。図６、図７は集合Ｓ＝
｛ａ1、・・・ａm｝のメモリ上での表現である。集合は
計算機上ではリスト、配列において順序を無視したもの
として表現できる。
【００６５】メモリの容量は、この図２から図７におけ
る配列が長ければ長いほど、すなわち扱う数が大きけれ
ば大きいほど、容量を要する。本発明ではこのメモリ必
要量を節約できる。以下、これを証明する。
る配列が長ければ長いほど、すなわち扱う数が大きけれ
ば大きいほど、容量を要する。本発明ではこのメモリ必
要量を節約できる。以下、これを証明する。
【００６６】まず、本実施例のフローチャートを図８、
図９に従って説明する。最初に、図８に示したように、
入力多項式集合Ｆが多項式入力部から入力される（Ｓ
１）。次に、入力多項式集合Ｆの各元の頭項の係数を割
らず、かつ未使用の素数ｐを選ぶ（Ｓ２）。そして、写
像φを、多項式ｆに対し、ｆの各係数をｐで割った剰余
に置き換えた多項式を対応させるものとして定義する
（Ｓ３）。
図９に従って説明する。最初に、図８に示したように、
入力多項式集合Ｆが多項式入力部から入力される（Ｓ
１）。次に、入力多項式集合Ｆの各元の頭項の係数を割
らず、かつ未使用の素数ｐを選ぶ（Ｓ２）。そして、写
像φを、多項式ｆに対し、ｆの各係数をｐで割った剰余
に置き換えた多項式を対応させるものとして定義する
（Ｓ３）。
【００６７】そして、ＧをＦに初期化し、Ｇp を、Ｇの
各元のφによる像の集合とし、Ｇから構成される全ての
多項式対からなる集合Ｄを作り（Ｓ４）、その後、以下
のＳ５からＳ１４までのループを繰り返す。
各元のφによる像の集合とし、Ｇから構成される全ての
多項式対からなる集合Ｄを作り（Ｓ４）、その後、以下
のＳ５からＳ１４までのループを繰り返す。
【００６８】次いで、Ｄから、規準により、計算するこ
となしに、０に正規化されることがわかっている元を取
り除く（Ｓ５）。Ｄが空集合か否か判定し（Ｓ６）、Ｄ
が空集合ならば、ループを抜け、Ｓ２１へ進む。Ｄが空
集合でなければ（Ｓ７）、Ｄから元Ｃを、規準により一
つ取り出し、残りを改めてＤとし、次いで、多項式対Ｃ
からＳ多項式Ｐを作る（Ｓ８）。
となしに、０に正規化されることがわかっている元を取
り除く（Ｓ５）。Ｄが空集合か否か判定し（Ｓ６）、Ｄ
が空集合ならば、ループを抜け、Ｓ２１へ進む。Ｄが空
集合でなければ（Ｓ７）、Ｄから元Ｃを、規準により一
つ取り出し、残りを改めてＤとし、次いで、多項式対Ｃ
からＳ多項式Ｐを作る（Ｓ８）。
【００６９】そして、φ（Ｐ）のＧpによる、ｐを法と
する正規化形式ＮＦ（φ（Ｐ），Ｇp）を計算して、Ｎ
Ｆ（φ（Ｐ），Ｇp）が０かどうか判定する（Ｓ１
０）。そして、Ｆ（φ（Ｐ），Ｇp）が０でない場合の
み、ＮＦ（Ｐ，Ｇ）を計算する（Ｓ１１）。ＮＦ（φ
（Ｐ），Ｇp）が０の場合、Ｓ５に戻る。
する正規化形式ＮＦ（φ（Ｐ），Ｇp）を計算して、Ｎ
Ｆ（φ（Ｐ），Ｇp）が０かどうか判定する（Ｓ１
０）。そして、Ｆ（φ（Ｐ），Ｇp）が０でない場合の
み、ＮＦ（Ｐ，Ｇ）を計算する（Ｓ１１）。ＮＦ（φ
（Ｐ），Ｇp）が０の場合、Ｓ５に戻る。
【００７０】もしＨＣ（ＮＦ（Ｐ，Ｇ））がｐで割り切
れるならば（Ｓ１３）、Ｓ２に戻る。そうでなければ、
Ｇの各元と、ＮＦ（Ｐ，Ｇ）からなる多項式対を全て、
Ｄに加える。このＳ１３では、グレブナ基底候補として
ふさわしいか否かのチェックが行うのである。さらに、
ＧにＮＦ（Ｐ，Ｇ）を加え、Ｇｐにφ（ＮＦ（Ｐ，
Ｇ））を加える（Ｓ１４）。その後Ｓ５に戻る。
れるならば（Ｓ１３）、Ｓ２に戻る。そうでなければ、
Ｇの各元と、ＮＦ（Ｐ，Ｇ）からなる多項式対を全て、
Ｄに加える。このＳ１３では、グレブナ基底候補として
ふさわしいか否かのチェックが行うのである。さらに、
ＧにＮＦ（Ｐ，Ｇ）を加え、Ｇｐにφ（ＮＦ（Ｐ，
Ｇ））を加える（Ｓ１４）。その後Ｓ５に戻る。
【００７１】ここで、有理数上の正規化形式が０でない
にも係わらず、法ｐの計算により０と判定してしまう場
合、このフローチャートではチェックできず、グレブナ
基底候補として出力される可能性があるが、Ｓ１３にお
いて、有理数上で計算された正規化形式の頭係数がｐで
割り切れるか否かを判定し、割り切れない場合にはｐを
取り直して計算し直しとなる。このことが、「有理数上
の正規化形式が０でないにもかかわらず、法ｐで０にな
るならば、有理数上の正規化形式の係数が全て法ｐで割
り切れる」ことを保証する。ｐが大きい場合、有理数上
の正規化形式の係数が全てｐで割り切れる確率は実質的
に０となる。これは、前記の可能性が実質的に０である
ことを示している。
にも係わらず、法ｐの計算により０と判定してしまう場
合、このフローチャートではチェックできず、グレブナ
基底候補として出力される可能性があるが、Ｓ１３にお
いて、有理数上で計算された正規化形式の頭係数がｐで
割り切れるか否かを判定し、割り切れない場合にはｐを
取り直して計算し直しとなる。このことが、「有理数上
の正規化形式が０でないにもかかわらず、法ｐで０にな
るならば、有理数上の正規化形式の係数が全て法ｐで割
り切れる」ことを保証する。ｐが大きい場合、有理数上
の正規化形式の係数が全てｐで割り切れる確率は実質的
に０となる。これは、前記の可能性が実質的に０である
ことを示している。
【００７２】以上により、Ｓ６でＤ＝空集合のとき、Ｇ
がグレブナ基底である蓋然性が高いものとして出力し、
メモリに蓄積する。これがグレブナ基底候補Ｇである。
図９では、図８の処理の結果得られたＧをグレブナ基底
とみなし、冗長な基底を取り除き、かつ相互正規化を行
ったものを改めてＧとする（Ｓ２１）。
がグレブナ基底である蓋然性が高いものとして出力し、
メモリに蓄積する。これがグレブナ基底候補Ｇである。
図９では、図８の処理の結果得られたＧをグレブナ基底
とみなし、冗長な基底を取り除き、かつ相互正規化を行
ったものを改めてＧとする（Ｓ２１）。
【００７３】そして、Ｇから生成した多項式対の内、規
準により０に正規化されることがわかっているもの以外
の対からＳ多項式を作り、Ｇによる正規化形式を計算
し、０に正規化されないものが出た時点で、Ｓ２に戻る
（Ｓ２２〜Ｓ２５）。
準により０に正規化されることがわかっているもの以外
の対からＳ多項式を作り、Ｇによる正規化形式を計算
し、０に正規化されないものが出た時点で、Ｓ２に戻る
（Ｓ２２〜Ｓ２５）。
【００７４】また、Ｆの各元のＧによる正規化形式を計
算し、０に正規化されないものがでた時点で、Ｓ２に戻
る（Ｓ２６〜Ｓ２９）。最後にＧを出力する（Ｓ３
０）。
算し、０に正規化されないものがでた時点で、Ｓ２に戻
る（Ｓ２６〜Ｓ２９）。最後にＧを出力する（Ｓ３
０）。
【００７５】図８、図９中、Ｓ１０が、モジュラ演算に
よる０への正規化のチェックであり、Ｓ２２〜Ｓ２５
が、グレブナ基底であることのチェック、Ｓ２６からＳ
２９が、入力イデアルと出力イデアルの同等性のチェッ
クである。
よる０への正規化のチェックであり、Ｓ２２〜Ｓ２５
が、グレブナ基底であることのチェック、Ｓ２６からＳ
２９が、入力イデアルと出力イデアルの同等性のチェッ
クである。
【００７６】このフローチャート中、簡約の計算と、正
規形の計算について説明する。まず、簡約の計算につい
て説明する。
規形の計算について説明する。まず、簡約の計算につい
て説明する。
【００７７】グレブナ基底計算に先だって、多項式の各
項の間には、次数に基づくある順序が定められる。そし
て、計算の途中に現れるすべての多項式の各項は、その
順序に従って、上→下の順で整列される。
項の間には、次数に基づくある順序が定められる。そし
て、計算の途中に現れるすべての多項式の各項は、その
順序に従って、上→下の順で整列される。
【００７８】ｆ＝ｃ1・ｔ1＋…＋ｃ1・ｔ1 ｔ1が先頭の項、すなわち頭項である。簡約とは、この
式を０と見なし、ｔ1を−１／ｃ1・（ｃ2・ｔ2＋…＋ｃ
1・ｔ1）で置き換える という操作を、ある多項式に対して行うことである。こ
こで、この置き換えは、ｔ1が割り切る項に対してのみ
行うことができる。すなわち、 ｇ＝ｄ1・ｓ1＋ｄ2・ｓ2＋…ｄk・ｓk＋…ｄ1・ｓ1 に対し、ｔ1｜ｓｋとなる場合に、ｇをｆにより簡約で
きる。この場合、簡約後のｇは、 ｇ−（ｄｋ／ｃ1）・（ｓk／ｔ1）・ｆ となる。ここで、係数の間の有利数演算が現れるが、実
際には、有理数演算は数多くの最大公約数の計算をする
必要があり、効率を著しく損なうため、 ｃ1／ｇ−ｄk・（ｓk／ｔ1）・ｆ なる簡約により、有理数演算が現れないようにする。こ
のようにすると、簡約結果は、先に定義したものの定数
倍となるが、実際には、得られた式を０とおいたものを
考えているので定数倍の差は影響ない。
式を０と見なし、ｔ1を−１／ｃ1・（ｃ2・ｔ2＋…＋ｃ
1・ｔ1）で置き換える という操作を、ある多項式に対して行うことである。こ
こで、この置き換えは、ｔ1が割り切る項に対してのみ
行うことができる。すなわち、 ｇ＝ｄ1・ｓ1＋ｄ2・ｓ2＋…ｄk・ｓk＋…ｄ1・ｓ1 に対し、ｔ1｜ｓｋとなる場合に、ｇをｆにより簡約で
きる。この場合、簡約後のｇは、 ｇ−（ｄｋ／ｃ1）・（ｓk／ｔ1）・ｆ となる。ここで、係数の間の有利数演算が現れるが、実
際には、有理数演算は数多くの最大公約数の計算をする
必要があり、効率を著しく損なうため、 ｃ1／ｇ−ｄk・（ｓk／ｔ1）・ｆ なる簡約により、有理数演算が現れないようにする。こ
のようにすると、簡約結果は、先に定義したものの定数
倍となるが、実際には、得られた式を０とおいたものを
考えているので定数倍の差は影響ない。
【００７９】次に、正規形の計算について説明する。
【００８０】正規形の計算（ＮＦ（ｆ，Ｇ））は、Ｇの
どの元の頭項によっても簡約できなくなるまで前節の簡
約を行うことによりえられる。この操作が、簡約を行な
う際のＧの元の選びかたによらず有限回で止まることは
保証されている。ただし、結果は、簡約のしかたにより
一般には一意的でない。
どの元の頭項によっても簡約できなくなるまで前節の簡
約を行うことによりえられる。この操作が、簡約を行な
う際のＧの元の選びかたによらず有限回で止まることは
保証されている。ただし、結果は、簡約のしかたにより
一般には一意的でない。
【００８１】係数として、通常の数値計算において用い
られる浮動小数を用いずに、任意桁の多倍長数(bignum)
を用いるのは、次のような理由による。・得られたグレ
ブナ基底は、数値解を求めやすい形をしており、しか
も、数値解の誤差も明確に評価できる。初めてから浮動
小数を用いて連立代数方程式の求解をすると、多くの場
合、得られた結果の精度が不明となる。・方程式の持つ
数学的な性質が保存されたまま式変形が行なわれる。数
値計算の場合、単なる数値が結果として得られるだけで
ある。・解が有限個でなく、いくつかのパラメタを含む
ような場合も扱える。このような場合は、数値計算はも
ともと無力である。
られる浮動小数を用いずに、任意桁の多倍長数(bignum)
を用いるのは、次のような理由による。・得られたグレ
ブナ基底は、数値解を求めやすい形をしており、しか
も、数値解の誤差も明確に評価できる。初めてから浮動
小数を用いて連立代数方程式の求解をすると、多くの場
合、得られた結果の精度が不明となる。・方程式の持つ
数学的な性質が保存されたまま式変形が行なわれる。数
値計算の場合、単なる数値が結果として得られるだけで
ある。・解が有限個でなく、いくつかのパラメタを含む
ような場合も扱える。このような場合は、数値計算はも
ともと無力である。
【００８２】図８、図９のフローチャートに従った、グ
レブナ基底計算における著名なテスト問題を以下に示
す。
レブナ基底計算における著名なテスト問題を以下に示
す。
【００８３】
【数１】Katsura5＝[u0＋2u1＋2u2＋2u3＋2u4＋2u5−1,
2u4u0＋(2u3＋2u5)u1＋u2 2−u4,2u3u0＋(2u2＋2u4)u1＋
2u5u2−u3,2u2u0＋u2 1＋2u3u1＋(2u4−1)u2＋2u5u3,2u1
u0＋(2u2−1)u1＋2u3u2＋2u4u3＋2u5u4,u2 0−u0＋2u2 1
＋2u2 2＋2u2 3＋2u2 4＋2u2 5］ order:u5＞u4＞u3＞u2＞u1＞u0
2u4u0＋(2u3＋2u5)u1＋u2 2−u4,2u3u0＋(2u2＋2u4)u1＋
2u5u2−u3,2u2u0＋u2 1＋2u3u1＋(2u4−1)u2＋2u5u3,2u1
u0＋(2u2−1)u1＋2u3u2＋2u4u3＋2u5u4,u2 0−u0＋2u2 1
＋2u2 2＋2u2 3＋2u2 4＋2u2 5］ order:u5＞u4＞u3＞u2＞u1＞u0
【００８４】
【数２】Katsura6＝[u0＋2u1＋2u2＋2u3＋2u4＋2u5＋2u
6−1,2u5u0＋(2u4＋2u6)u1＋2u3u2−u5,2u4u0＋(2u3＋2
u5)u1＋u2 2＋2u6u2−u4,2u3u0＋(2u2＋2u4)u1＋2u5u2＋
(2u6−1)u3,2u2u0＋u2 1＋2u3u1＋(2u4−1)u2＋2u5u3＋2
u6u4,2u1u0＋(2u2−1)u1＋2u3u2＋2u4u3＋2u5u4＋2u
6u5,u2 0−u0＋2u2 1＋2u2 2＋2u2 3＋2u2 4＋2u2 5＋2u2 6］ order:u6＞u5＞u4＞u3＞u2＞u1＞u0
6−1,2u5u0＋(2u4＋2u6)u1＋2u3u2−u5,2u4u0＋(2u3＋2
u5)u1＋u2 2＋2u6u2−u4,2u3u0＋(2u2＋2u4)u1＋2u5u2＋
(2u6−1)u3,2u2u0＋u2 1＋2u3u1＋(2u4−1)u2＋2u5u3＋2
u6u4,2u1u0＋(2u2−1)u1＋2u3u2＋2u4u3＋2u5u4＋2u
6u5,u2 0−u0＋2u2 1＋2u2 2＋2u2 3＋2u2 4＋2u2 5＋2u2 6］ order:u6＞u5＞u4＞u3＞u2＞u1＞u0
【００８５】
【数３】Cyclic6＝［c5c4c3c2c1c0−1,((((c4＋c5)c3＋
c5c4)c2＋c5c4c3)c1＋c5c4c3c2)c0＋c5c4c3c2c1,(((c3
＋c5)c2＋c5c4)c1＋c5c4c3)c0＋c4c3c2c1＋c5c4c3c2,
((c2＋c5)c1＋c5c4)c0＋c3c2c1＋c4c3c2＋c5c4c3,(c1＋
c5)c0＋c2c1＋c3c2＋c4c3＋c5c4,c0＋c1＋c2＋c3＋c4＋
c5］ order:c0＞c1＞c2＞c3＞c4＞c5
c5c4)c2＋c5c4c3)c1＋c5c4c3c2)c0＋c5c4c3c2c1,(((c3
＋c5)c2＋c5c4)c1＋c5c4c3)c0＋c4c3c2c1＋c5c4c3c2,
((c2＋c5)c1＋c5c4)c0＋c3c2c1＋c4c3c2＋c5c4c3,(c1＋
c5)c0＋c2c1＋c3c2＋c4c3＋c5c4,c0＋c1＋c2＋c3＋c4＋
c5］ order:c0＞c1＞c2＞c3＞c4＞c5
【００８６】
【数４】Lazard＝［cba2＋(cb2＋(c2＋c＋1)b＋c)a＋c
b,(cb2＋cb)a2＋(c2b2＋cb＋1)a＋cb＋c,(c2＋c)b2a2＋
(cb2＋cb＋c)a＋c＋1］ order:a＞b＞c
b,(cb2＋cb)a2＋(c2b2＋cb＋1)a＋cb＋c,(c2＋c)b2a2＋
(cb2＋cb＋c)a＋c＋1］ order:a＞b＞c
【００８７】
【数５】Arnborg＝［a＋b＋c＋d＋e,(b＋e)a＋cb＋dc＋
ed,((c+e)b＋ed)a＋dcb＋edc,((ec＋ed)b＋edc)a＋(e＋
1)dcb,edcba−1］ order:a＞b＞c＞d＞e 表１は、上記の各問題について、通常の算法による計算
結果と、本発明の改良を採り入れた算法による計算結果
を対比させたものである。
ed,((c+e)b＋ed)a＋dcb＋edc,((ec＋ed)b＋edc)a＋(e＋
1)dcb,edcba−1］ order:a＞b＞c＞d＞e 表１は、上記の各問題について、通常の算法による計算
結果と、本発明の改良を採り入れた算法による計算結果
を対比させたものである。
【００８８】ここで、計算プログラムは、発明者らが開
発中の数式処理システムRisa／Asir上にインプリメント
された。計算機は、Sony NEWS5000(R4000 CPU、50MHz)を
用いた。いずれの例も、計算途中に中間式の大きな係数
膨張が生ずるため、既存の数式処理システムでは計算不
可能、あるいは極めて長大な計算時間を必要とする例で
ある。表１で明らかなように、ここで挙げた問題に対し
ては、本発明による改良は顕著な効果を表している。
発中の数式処理システムRisa／Asir上にインプリメント
された。計算機は、Sony NEWS5000(R4000 CPU、50MHz)を
用いた。いずれの例も、計算途中に中間式の大きな係数
膨張が生ずるため、既存の数式処理システムでは計算不
可能、あるいは極めて長大な計算時間を必要とする例で
ある。表１で明らかなように、ここで挙げた問題に対し
ては、本発明による改良は顕著な効果を表している。
【００８９】
【表１】 ここで、Ｎｏ．１はKatsura5、Ｎｏ．２はKatsura6、Ｎ
ｏ．３はCyclic6、Ｎｏ．４はCyclic6、Ｎｏ．５はLaza
rd、Ｎｏ．６はArnborgの実験例を示す。
ｏ．３はCyclic6、Ｎｏ．４はCyclic6、Ｎｏ．５はLaza
rd、Ｎｏ．６はArnborgの実験例を示す。
【００９０】Totalは全ＣＰＵtime 、ＮＦ／Ｑは有理数
上での正規化、ＮＦ／ｐは法ｐでの正規化、ＧＢはグレ
ブナ基底チェック（アルゴリズムの（１）の第１０
項）、Memberはイデアルの同等性チェック（アルゴリズ
ム（１）の第１１項）に対するＣＰＵtimeである。単位
は全て秒である。
上での正規化、ＮＦ／ｐは法ｐでの正規化、ＧＢはグレ
ブナ基底チェック（アルゴリズムの（１）の第１０
項）、Memberはイデアルの同等性チェック（アルゴリズ
ム（１）の第１１項）に対するＣＰＵtimeである。単位
は全て秒である。
【００９１】比は＜改良前のTotal＞／＜改良後のTotal
＞で、改良によるスピードアップを示す。各計算におい
て、法ｐとして１００９をとって計算を始めているが、
全ての例で、この法により正しいグレナブ基底が得られ
た。optionにおいて、lex は辞書式順序、revlexは全次
数逆辞書式順序を表し、homoは、homogenizationを経由
してグレブナ基底を求めたことを示す。また、数字の入
っていないものは、改良後の計算に比べて極端に時間が
かかることが計算中に推測されたため、中断したもので
ある。
＞で、改良によるスピードアップを示す。各計算におい
て、法ｐとして１００９をとって計算を始めているが、
全ての例で、この法により正しいグレナブ基底が得られ
た。optionにおいて、lex は辞書式順序、revlexは全次
数逆辞書式順序を表し、homoは、homogenizationを経由
してグレブナ基底を求めたことを示す。また、数字の入
っていないものは、改良後の計算に比べて極端に時間が
かかることが計算中に推測されたため、中断したもので
ある。
【００９２】また、この表１の結果を、１９９３年の１
月当時と比較すると、以下の表２のようになる。
月当時と比較すると、以下の表２のようになる。
【００９３】
【表２】 *homogenization なしの値 このように、９３年１月当時からすると、一段と速度が
向上している。これは本発明によりメモリ節約が効率よ
く行われた結果と推定される。
向上している。これは本発明によりメモリ節約が効率よ
く行われた結果と推定される。
【００９４】メモリ使用状況を見てみると、以下のよう
なことがいえる。
なことがいえる。
【００９５】今回の改良により、時間だけでなく、必要
とされるメモリも減らすことができる。ガーベジコレク
タにより不必要になったメモリが回収されるため、実際
に必要なメモリの絶対量は必ずしも大幅に減少はしない
が、プログラムがシステムに要求するメモリの総和は、
以下の表３が示すように確かに減少する。
とされるメモリも減らすことができる。ガーベジコレク
タにより不必要になったメモリが回収されるため、実際
に必要なメモリの絶対量は必ずしも大幅に減少はしない
が、プログラムがシステムに要求するメモリの総和は、
以下の表３が示すように確かに減少する。
【００９６】
【表３】 単位：ＭＢ 時間の比較と同様、katsura6 と Arnborg に関しては、
改良前の版での計算が実質上不可能のため、比較は行な
っていない。Arnborg に関しては、数時間後に計算を中
断した時点で、カウンタ(32bit)の許容範囲を越えてい
た。その時点で、最低でも一桁以上多いメモリが必要に
なっていたと考えられる。
改良前の版での計算が実質上不可能のため、比較は行な
っていない。Arnborg に関しては、数時間後に計算を中
断した時点で、カウンタ(32bit)の許容範囲を越えてい
た。その時点で、最低でも一桁以上多いメモリが必要に
なっていたと考えられる。
【００９７】メモリは図１０に示したように、本発明で
は、経時的にも少ない使用量ですむ。従来では、結果の
表現に必要なメモリ量に比較して、計算途中に急激にメ
モリ使用量が増えるので、そのピークを予測しずらく、
メモリ資源の有効利用が計れない。
は、経時的にも少ない使用量ですむ。従来では、結果の
表現に必要なメモリ量に比較して、計算途中に急激にメ
モリ使用量が増えるので、そのピークを予測しずらく、
メモリ資源の有効利用が計れない。
【００９８】以上で説明したように、本発明によれば、
０に正規化されるＳ多項式を有理数上で正規化した場合
に大きな係数膨張が生ずるような問題に対しても、モジ
ュラ計算により係数膨張を回避でき、しかも、結果の正
当性の確認が容易であるため、既存の方法に比較して高
速にグレブナ基底を生成でき、代数方程式の高速な求解
に寄与するところが大きい。
０に正規化されるＳ多項式を有理数上で正規化した場合
に大きな係数膨張が生ずるような問題に対しても、モジ
ュラ計算により係数膨張を回避でき、しかも、結果の正
当性の確認が容易であるため、既存の方法に比較して高
速にグレブナ基底を生成でき、代数方程式の高速な求解
に寄与するところが大きい。
【００９９】そして、モジュラ演算を用いることにより
計算コストを大幅に下げ、かつ、従来困難であった結果
の正当性の確認を容易にした、正当かつ実用的なグレブ
ナ基底生成法を提供できる。
計算コストを大幅に下げ、かつ、従来困難であった結果
の正当性の確認を容易にした、正当かつ実用的なグレブ
ナ基底生成法を提供できる。
【０１００】＜実施例２＞本実施例は、斉次化と本発明
におけるモジュラ演算を組み合わせた場合の例であり、
図１１に示したように、対象となる多項式集合Ｆを予め
斉次化する斉次化手段３０と、最終的に得られた多項式
集合Ｆ1 を非斉次化する非斉次化手段３１とを備えてお
り、他は実施例１と同一である。
におけるモジュラ演算を組み合わせた場合の例であり、
図１１に示したように、対象となる多項式集合Ｆを予め
斉次化する斉次化手段３０と、最終的に得られた多項式
集合Ｆ1 を非斉次化する非斉次化手段３１とを備えてお
り、他は実施例１と同一である。
【０１０１】表４に、斉次化と本発明におけるモジュラ
演算を組み合わせた場合の例を、斉次化をしない場合、
モジュラ計算をしない場合と比較して示す。
演算を組み合わせた場合の例を、斉次化をしない場合、
モジュラ計算をしない場合と比較して示す。
【０１０２】
【表４】 計算機は、Ｓｏｎｙ ＮＥＷＳ５０００（Ｒ４０００
ＣＰＵ，５０ＭＨｚ）を用いた。
ＣＰＵ，５０ＭＨｚ）を用いた。
【０１０３】表４で用いた方程式を以下に示す。以下に
おいて、Ａn はｎ変数 Arnborg systemを示し、Ａ5か
らＭＡ5までは、変数順序はアルファベット順である。 Ａ5 ｛edcba-1,(((d+e)c+ed)b+edc)a+edcb,((c+e)b+ed)a+dcb+edc, (b+e)a+cb+dc+ed,a+b+c+d+e｝ Ａ6 ｛fedcba-1,((((e+f)d+fe)c+fed)b+fedc)a+fedcb,(((d+f)c+fe)b+fed)a+ edcb+fedc,((c+f)b+fe)a+dcb+edc+fed,(b+f)a+cb+dc+ed+fe,a+b+c+d+e+f ｝ Ａ7 ｛gfedcba-1,(((((f+g)e+gf)d+gfe)c+gfed)b+gfedc)a+gfedcb,((((e+g)d+ gf)c+gfe)b+gfed)a+fedcb+gfedc,(((d+g)c+gf)b+gfe)a+edcb+fedc+gfed, ((c+d)b+gf)a+dcb+edc+fed+gfe,(b+g)a+cb+dc+ed+fe+gf,a+b+c+d+e+f+g ｝ ＭＡ7 ｛a2bc+ab2c+abc2+abc+ab+ac+bc,a2b2c+ab2c2+a2bc+abc+bc+a+c,a2b2c2+ a2b2c+ab2c+abc+ac+c+1} ＭＡ5 ｛a+b+c+d+e,ab+bc+cd+de+ea,abc+bcd+cde+dea+eab,bcd+bcde+cdea+ deab+eabc,abcde-1} Ｋnは ｎ＋１変数 Katsura system である。
おいて、Ａn はｎ変数 Arnborg systemを示し、Ａ5か
らＭＡ5までは、変数順序はアルファベット順である。 Ａ5 ｛edcba-1,(((d+e)c+ed)b+edc)a+edcb,((c+e)b+ed)a+dcb+edc, (b+e)a+cb+dc+ed,a+b+c+d+e｝ Ａ6 ｛fedcba-1,((((e+f)d+fe)c+fed)b+fedc)a+fedcb,(((d+f)c+fe)b+fed)a+ edcb+fedc,((c+f)b+fe)a+dcb+edc+fed,(b+f)a+cb+dc+ed+fe,a+b+c+d+e+f ｝ Ａ7 ｛gfedcba-1,(((((f+g)e+gf)d+gfe)c+gfed)b+gfedc)a+gfedcb,((((e+g)d+ gf)c+gfe)b+gfed)a+fedcb+gfedc,(((d+g)c+gf)b+gfe)a+edcb+fedc+gfed, ((c+d)b+gf)a+dcb+edc+fed+gfe,(b+g)a+cb+dc+ed+fe+gf,a+b+c+d+e+f+g ｝ ＭＡ7 ｛a2bc+ab2c+abc2+abc+ab+ac+bc,a2b2c+ab2c2+a2bc+abc+bc+a+c,a2b2c2+ a2b2c+ab2c+abc+ac+c+1} ＭＡ5 ｛a+b+c+d+e,ab+bc+cd+de+ea,abc+bcd+cde+dea+eab,bcd+bcde+cdea+ deab+eabc,abcde-1} Ｋnは ｎ＋１変数 Katsura system である。
【０１０４】条件 zp=z-p and zp=0(｜p｜＞n)のもとで
次のように定義される。 ｛zp-Σn i=-nzizp-i(p=0,・・・n-1),Σn p=-nzp-1｝ 変数順序：｛zn,zn-1,・・・,z0｝ Ｒose は Rose system である。
次のように定義される。 ｛zp-Σn i=-nzizp-i(p=0,・・・n-1),Σn p=-nzp-1｝ 変数順序：｛zn,zn-1,・・・,z0｝ Ｒose は Rose system である。
【０１０５】 {u4 4-20/7a46 2, a46 2u3 4+7/10a46u3 4+7/48u3 4-50/27a46 2-35/27a46-49/216, a46 5u4 3+7/5a46 4u4 3+609/1000a46 3u4 3+49/1250a46 2u4 3 -27391/800000a46u4 3-1029/160000u4 3+3/7a46 5u3u4 2+3/5a46 6u3u4 2 +63/200a46 3u3u4 2+147/2000a46 2u3u4 2+4137/800000a46u3u4 2 -7/20a46 4u3 2u4-77/125a46 3u3 2u4-23863/60000a46 2u3 2u4 -1078/9375a46u3 2u4-24353/1920000u3 2u4-3/20a46 4u3 3-21/100a46 3u3 3 -91/800a46 2u3 3-5887/200000a46u3 3-343/128000u3 3} 変数順序：｛u3,u4,a46｝ 表４のモジュラ演算、非モジュラ演算の項は、それぞれ
のアルゴリズムによる計算時間で、単位は秒、オプショ
ンの項において、Ｌは辞書式順序、Ｒは全次数逆辞書式
順序、Ｈは斉次化を示す。
のアルゴリズムによる計算時間で、単位は秒、オプショ
ンの項において、Ｌは辞書式順序、Ｒは全次数逆辞書式
順序、Ｈは斉次化を示す。
【０１０６】比は＜非モジュラの実行時間／モジュラの
実行時間＞で、モジュラ演算による効果を示す。表４の
比の項で、＞ｎは、いくつかの不必要対を実際に正規化
してみた結果から推測した値で、実際にはさらに大きな
値になると考えられる。
実行時間＞で、モジュラ演算による効果を示す。表４の
比の項で、＞ｎは、いくつかの不必要対を実際に正規化
してみた結果から推測した値で、実際にはさらに大きな
値になると考えられる。
【０１０７】表４に挙げた例に対しては、Ｋ5をのぞ
き、斉次化を行わずにグレブナ基底を計算することはし
ていない。とくに、斉次化を行わない場合、使用メモリ
量が膨大になりついには計算不能になる場合が多い。Ｋ
5 に対する結果では、斉次化により１０倍程度の高速化
が達成されているところからみて、Ｋ6，Ａ7等のさらに
大きな問題では、より大きな比になると考えられる。
き、斉次化を行わずにグレブナ基底を計算することはし
ていない。とくに、斉次化を行わない場合、使用メモリ
量が膨大になりついには計算不能になる場合が多い。Ｋ
5 に対する結果では、斉次化により１０倍程度の高速化
が達成されているところからみて、Ｋ6，Ａ7等のさらに
大きな問題では、より大きな比になると考えられる。
【０１０８】以上により、モジュラ演算と斉次化の組み
合わせは、モジュラ演算単独の場合に比較して、さらに
広い範囲の問題に対して高速なグレブナ基底生成法を与
えることができる。
合わせは、モジュラ演算単独の場合に比較して、さらに
広い範囲の問題に対して高速なグレブナ基底生成法を与
えることができる。
【０１０９】なお、実施例２における演算のアルゴリズ
ムを以下に列挙する。これらによるグレブナ基底演算
は、斉次化を除き実施例１と同様である。 ＜モジュラ演算（斉次化なし）＞ modular grobner(Ｆ) Input:Ａ polynomial set Ｆ⊂Ｚ［x1,・・・,xn］ Output:The redused Grobner basis Ｇ of Id(Ｆ) in Ｑ［x1,・・・,xn］ ａｇａｉｎ： ｐ←a new prime （素数ｐを選ぶ） Ｇ←modular grobner candidate(Ｆ，ｐ) （グレブナ基底候補生成） if Ｇ＝ｆａｉｌｕｒｅ then goto again （グレブナ基底候補チェック、 候補でないとき再度演算） Ｇ←grobner test(Ｆ，Ｇ) （グレブナ基底チェック） if Ｇ＝ｆａｉｌｕｒｅ then goto again （グレブナ基底でないとき再度演 算） return Ｇ ＜モジュラ演算（斉次化伴う）＞ modular grobner with homogenization(Ｆ) Input:Ａ polynomial set Ｆ Output:The redused Grobner basis Ｇ of Id(Ｆ) define the appropriate ordering in Ｒh according to the ordering in Ｒ ａｇａｉｎ： ｐ←a new prime Ｇ←modular mrobner candidate(Ｆ*，ｐ) （斉次化） if Ｇ＝ｆａｉｌｕｒｅ then goto again Ｇ←grobner test(Ｆ，Ｇ*) （非斉次化） if Ｇ＝ｆａｉｌｕｒｅ then goto again return Ｇ （ Ｆ*：homogenization；Ｇ*：dehomogenization ） ＜グレブナー基底候補の生成＞ modular grobner candidate(Ｆ，ｐ) Input:Ａ polynomial set Ｆ；a prime ｐ Output:Ａ candidate of a Grobner basis Ｇ of Id(Ｆ) or ｆａｉｌｕｒｅ if∃ｆ∈Ｆs.t. ¬Ｖａｌｉｄ（ｐ，ｆ）then return ｆａｉｌｕｒｅ Ｇ←Ｆ；Ｇp←｛φ（ｆ）｜ｆ∈Ｇ｝ Ｄ←｛｛ｆ，ｇ｝｜ｆ，ｇ∈Ｇ；ｆ≠ｇ｝（入力多項式集合Ｆから構成される 全ての多項式対からなる集合Ｄを 作る。） repeat｛ Ｄ←Ｄ＼Ｕseless Ｐairs （Ｄ） （Ｄから、ある規準により、計算す ることなしに、０に正規化される ことがわかっている元を取り除く ） if Ｄ＝Void Set then return Ｇ （Ｄが空集合ならば、Ｆを出 力する） else｛Ｃ←Ｓelect Ｐair（Ｄ）；Ｄ←Ｄ＼｛Ｃ｝｝ Ｐ←Ｓpoly（Ｃ） （多項式対ＣからＳ多項式Ｐを作 り、 Ｆにより正規化し、Ｐの正 規化を ＮＦ（Ｐ，Ｆ）と書く） (1) if ＮＦ（φ（Ｐ）,Ｇp）≠０ then｛ （多項式対の正規化形式を、ｐを 法として計算する） (2) ｔ←ＮＦ（Ｐ,Ｇ） if ¬Ｖａｌｉｄ（ｐ，ｔ）then return ｆａｉｌｕｒｅ Ｄ←Ｄ∪｛｛ｆ，ｔ｝｜ｆ∈Ｇ｝ Ｇ←Ｇ∪｛ｔ｝；Ｇp←Ｇp∪｛φ（ｔ）｝ （法ｐでの正規化形式が０でな い場合のみ有理数上で正規化 形式を計算する） ｝ ｝ なお、¬Ｖａｌｉｄ＝ｎｏｔ Ｖａｌｉｄの意味である。 ＜グレブナ基底チェック＞ grobner test（Ｆ，Ｇ） Input:Polynomial sets Ｆ,Ｇ s.t.Ｉｄ（Ｇ）⊂Ｉｄ（Ｆ） Output:The redused Grobner basis of Ｆ or ｆａｉｌｕｒｅ （Ｒ1）Ｇ←Ｇ＼｛ｇ∈Ｇ｜∃ｈ∈Ｇ＼｛ｇ｝s.t.ＨＴ（ｈ）｜ＨＴ（ｇ）｝ （集合Ｇをグレブナ基底とみて、冗長な基底を取り除く） （Ｒ2）Ｇ←Ｉnter Ｒeduce（Ｇ）＝｛ＮＦ（ｇ,Ｇ）＼｛ｇ｝｜ｇ∈Ｇ｝ （Ｇから一つのｇを取出し、ｇ以外の元でｇを正規化する） （Ｃ1）Ｄ←｛｛ｆ，ｇ｝ｆ，ｇ∈Ｇ；ｆ≠ｇ｝ Ｄ←Ｄ＼Ｕseless Ｐairs （Ｄ） if∃｛ｆ，ｇ｝∈Ｄ s.t.ＮＦ（Ｓpoly（ｆ，ｇ）,Ｇ）≠０ then return ｆａｉｌｕｒｅ （Ｄから規準により０に正規化されることがわかっている対を取り除く Ｄの各対からＳ多項式を作り、Ｇにより正規化し、０でないものが出た ら再度演算） （Ｃ2）if∃ｆ∈Ｆ s.t.ＮＦ（ｆ,Ｇ）≠０ then return ｆａｉｌｕｒｅ return Ｇ （Ｆの各元をＧにより正規化し、０でないものが出たら再度演算） 以上のアルゴリズムにおいて以下の事項が参照される。
ムを以下に列挙する。これらによるグレブナ基底演算
は、斉次化を除き実施例１と同様である。 ＜モジュラ演算（斉次化なし）＞ modular grobner(Ｆ) Input:Ａ polynomial set Ｆ⊂Ｚ［x1,・・・,xn］ Output:The redused Grobner basis Ｇ of Id(Ｆ) in Ｑ［x1,・・・,xn］ ａｇａｉｎ： ｐ←a new prime （素数ｐを選ぶ） Ｇ←modular grobner candidate(Ｆ，ｐ) （グレブナ基底候補生成） if Ｇ＝ｆａｉｌｕｒｅ then goto again （グレブナ基底候補チェック、 候補でないとき再度演算） Ｇ←grobner test(Ｆ，Ｇ) （グレブナ基底チェック） if Ｇ＝ｆａｉｌｕｒｅ then goto again （グレブナ基底でないとき再度演 算） return Ｇ ＜モジュラ演算（斉次化伴う）＞ modular grobner with homogenization(Ｆ) Input:Ａ polynomial set Ｆ Output:The redused Grobner basis Ｇ of Id(Ｆ) define the appropriate ordering in Ｒh according to the ordering in Ｒ ａｇａｉｎ： ｐ←a new prime Ｇ←modular mrobner candidate(Ｆ*，ｐ) （斉次化） if Ｇ＝ｆａｉｌｕｒｅ then goto again Ｇ←grobner test(Ｆ，Ｇ*) （非斉次化） if Ｇ＝ｆａｉｌｕｒｅ then goto again return Ｇ （ Ｆ*：homogenization；Ｇ*：dehomogenization ） ＜グレブナー基底候補の生成＞ modular grobner candidate(Ｆ，ｐ) Input:Ａ polynomial set Ｆ；a prime ｐ Output:Ａ candidate of a Grobner basis Ｇ of Id(Ｆ) or ｆａｉｌｕｒｅ if∃ｆ∈Ｆs.t. ¬Ｖａｌｉｄ（ｐ，ｆ）then return ｆａｉｌｕｒｅ Ｇ←Ｆ；Ｇp←｛φ（ｆ）｜ｆ∈Ｇ｝ Ｄ←｛｛ｆ，ｇ｝｜ｆ，ｇ∈Ｇ；ｆ≠ｇ｝（入力多項式集合Ｆから構成される 全ての多項式対からなる集合Ｄを 作る。） repeat｛ Ｄ←Ｄ＼Ｕseless Ｐairs （Ｄ） （Ｄから、ある規準により、計算す ることなしに、０に正規化される ことがわかっている元を取り除く ） if Ｄ＝Void Set then return Ｇ （Ｄが空集合ならば、Ｆを出 力する） else｛Ｃ←Ｓelect Ｐair（Ｄ）；Ｄ←Ｄ＼｛Ｃ｝｝ Ｐ←Ｓpoly（Ｃ） （多項式対ＣからＳ多項式Ｐを作 り、 Ｆにより正規化し、Ｐの正 規化を ＮＦ（Ｐ，Ｆ）と書く） (1) if ＮＦ（φ（Ｐ）,Ｇp）≠０ then｛ （多項式対の正規化形式を、ｐを 法として計算する） (2) ｔ←ＮＦ（Ｐ,Ｇ） if ¬Ｖａｌｉｄ（ｐ，ｔ）then return ｆａｉｌｕｒｅ Ｄ←Ｄ∪｛｛ｆ，ｔ｝｜ｆ∈Ｇ｝ Ｇ←Ｇ∪｛ｔ｝；Ｇp←Ｇp∪｛φ（ｔ）｝ （法ｐでの正規化形式が０でな い場合のみ有理数上で正規化 形式を計算する） ｝ ｝ なお、¬Ｖａｌｉｄ＝ｎｏｔ Ｖａｌｉｄの意味である。 ＜グレブナ基底チェック＞ grobner test（Ｆ，Ｇ） Input:Polynomial sets Ｆ,Ｇ s.t.Ｉｄ（Ｇ）⊂Ｉｄ（Ｆ） Output:The redused Grobner basis of Ｆ or ｆａｉｌｕｒｅ （Ｒ1）Ｇ←Ｇ＼｛ｇ∈Ｇ｜∃ｈ∈Ｇ＼｛ｇ｝s.t.ＨＴ（ｈ）｜ＨＴ（ｇ）｝ （集合Ｇをグレブナ基底とみて、冗長な基底を取り除く） （Ｒ2）Ｇ←Ｉnter Ｒeduce（Ｇ）＝｛ＮＦ（ｇ,Ｇ）＼｛ｇ｝｜ｇ∈Ｇ｝ （Ｇから一つのｇを取出し、ｇ以外の元でｇを正規化する） （Ｃ1）Ｄ←｛｛ｆ，ｇ｝ｆ，ｇ∈Ｇ；ｆ≠ｇ｝ Ｄ←Ｄ＼Ｕseless Ｐairs （Ｄ） if∃｛ｆ，ｇ｝∈Ｄ s.t.ＮＦ（Ｓpoly（ｆ，ｇ）,Ｇ）≠０ then return ｆａｉｌｕｒｅ （Ｄから規準により０に正規化されることがわかっている対を取り除く Ｄの各対からＳ多項式を作り、Ｇにより正規化し、０でないものが出た ら再度演算） （Ｃ2）if∃ｆ∈Ｆ s.t.ＮＦ（ｆ,Ｇ）≠０ then return ｆａｉｌｕｒｅ return Ｇ （Ｆの各元をＧにより正規化し、０でないものが出たら再度演算） 以上のアルゴリズムにおいて以下の事項が参照される。
【０１１０】
【数６】
【０１１１】
【発明の効果】本発明では、単に高速にグレブナ基底を
生成できるという計算上の特徴を有するだけではなく、
コンピュータにおけるハード資産であるメモリ容量を少
なくできる。従来の方法によれば、得るべきグレブナ基
底の最終結果が予想できないことと、通常中間式が巨大
な桁数となることから、予め大容量のメモリを設定して
おかなければならず、資源の無駄になる。これに対し、
本発明では、メモリ容量を節約でき、かつ、高速演算に
資することができる。
生成できるという計算上の特徴を有するだけではなく、
コンピュータにおけるハード資産であるメモリ容量を少
なくできる。従来の方法によれば、得るべきグレブナ基
底の最終結果が予想できないことと、通常中間式が巨大
な桁数となることから、予め大容量のメモリを設定して
おかなければならず、資源の無駄になる。これに対し、
本発明では、メモリ容量を節約でき、かつ、高速演算に
資することができる。
【図１】 本発明の概念ブロック図
【図２】 自然数のメモリ上の表現を示す図
【図３】 有理数のメモリ上の表現を示す図
【図４】 項のメモリ上の表現を示す図
【図５】 多項式のメモリ上の表現を示す図
【図６】 集合Ｓ＝｛ａ1、・・・ａm｝のリストによる
メモリ上での表現
メモリ上での表現
【図７】 集合Ｓ＝｛ａ1、・・・ａm｝の配列によるメ
モリ上での表現
モリ上での表現
【図８】 本発明のフローチャート１を示す図
【図９】 本発明のフローチャート２を示す図
【図１０】 新旧におけるメモリ使用量の経時変化を示
す図
す図
【図１１】 実施例２を示す概念ブロック図
【符号の説明】 １・・多項式入力部 ２・・演算部 ３・・メモリ ４・・メモリ節約部 ５・・素数選択手段 ６・・第１の演算手段 ７・・判定手段 ８・・第２の演算手段 ９・・省略手段 １０・・グレブナ基底候補チェック手段 ２０・・グレブナ基底チェック手段 ２１・・グレブナ基底判定手段 ２２・・再演算制御手段 ３０・・斉次化手段 ３１・・非斉次化手段
Claims (10)
- 【請求項１】 パラメータ間の制約が連立代数方程式で
与えられるモデルにつき、該連立方程式を表すとともに
メモリ中に記述されている多項式集合Ｆからグレブナ基
底を生成するブッフバーガー演算をする計算機であり、 素数ｐを選ぶ素数選択手段（５）と、 多項式対の正規化形式を、ｐを法として計算する第１の
演算手段（６）と、 前記法ｐでの正規化形式が０か否かを判定する判定手段
（７）と、 この判定手段により前記法ｐでの正規化形式が０でない
と判定されたとき有理数上で前記正規化形式を計算する
第２の演算手段（８）と、 前記判定手段により前記法ｐでの正規化形式が０と判断
されたとき有理数上でも０とみなして、有理数上での正
規化形式の計算を省略する省略手段（９）と、を有する
メモリ節約制御部（４）を備え、 最終的に生成された多項式集合Ｆ1 を、グレブナ基底候
補として得ることを特徴とするグレブナ基底生成装置。 - 【請求項２】 請求項１において、得られた多項式集合
Ｆ1 から生成した多項式対の正規化形式を計算すること
によるグレブナ基底チェック手段と、 多項式集合Ｆの元全てがＦ1 により０に正規化されるこ
とを確かめることによるイデアルの同等性チェックによ
り、”Ｆ1 から生成したすべての多項式対のＳ多項式及
びＦのすべてが元がＦ1により０に正規化される”と
き、Ｆ1がＦのグレブナ基底であると判定するグレブナ
基底判定手段（２１）と、 このグレブナ基底判定手段による判定に失敗した場合、
前記素数選択手段による素数ｐをとり直して再度多項式
集合Ｆ1を得る再演算制御手段（２２）と、 を備えたグレブナ基底生成装置。 - 【請求項３】 請求項１において、第２の演算手段
（８）は、前記第１の演算手段（６）で得た、法ｐでの
正規化形式が０でないと判断されたとき、その都度直ち
に有理数上で前記正規化形式を計算することを特徴とす
るグレブナ基底生成装置。 - 【請求項４】 請求項３において、グレブナ基底候補の
頭係数を素数ｐで割り切れるか否かを判定し、割り切れ
ない場合のみグレブナ基底候補として出力するグレブナ
基底候補チェック手段を有することを特徴とするグレブ
ナ基底生成装置。 - 【請求項５】 請求項１から４において、対象となる多
項式集合Ｆを予め斉次化する斉次化手段と、 最終的に得られた多項式集合Ｆ1 を非斉次化する非斉次
化手段とを備えたことを特徴とするグレブナ基底生成装
置。 - 【請求項６】 入力多項式集合Ｆから構成される全ての
多項式対からなる集合Ｄを作ったのち、 Ｄから、ある規準により、計算することなしに、０に
正規化されることがわかっている元を取り除き、 Ｄが空集合ならば、Ｆの計算を続行し、Ｄが空集合で
なければ、Ｄから元Ｃを、ある規準により一つ取り出
し、残りを改めてＤとし、 多項式対ＣからＳ多項式Ｐを作り、Ｆにより正規化
し、Ｐの正規化をＮＦ（Ｐ，Ｆ）と書き、 ＮＦ（Ｐ，Ｆ）が０でないならば、Ｆの各元と、ＮＦ
（Ｐ，Ｆ）からなる多項式対を全て、Ｄに加え、さら
に、ＦにＮＦ（Ｐ，Ｆ）を加え、 これらからを繰り返すことにより、」パラメータ間
の制約が連立代数方程式で与えられるモデルについて、
該連立方程式を表す、メモリ中に記述されている多項式
集合Ｆからグレブナ基底を生成するブッフバーガー演算
をする計算機において、 ａ）素数ｐを選び、 ｂ）多項式対の正規化形式を、ｐを法として計算し、 ｃ）法ｐでの正規化形式が０でない場合のみ有理数上で
正規化形式を計算し、 ｄ）法ｐでの正規化形式が０の場合は有理数上でも０と
みなして、有理数上での正規化形式の計算を省略し、 ｅ）グレブナ基底の候補である多項式集合Ｆ1 を得るこ
とを特徴とするグレブナ基底生成方法。 - 【請求項７】 請求項６において、 ｅ）最終的に生成された、グレブナ基底とは限らない多
項式を含む多項式集合Ｆ1について、 ｅ−１）Ｆ1 から生成した多項式対の正規化形式を計算
することによるグレブナ基底チェックと、 ｅ−２）Ｆの元全てがＦ1 により０に正規化されること
を確かめることによるイデアルの同等性チェックを行う
ことにより、 ”Ｆ1 から生成したすべての多項式対のＳ多項式及びＦ
のすべてが元がＦ1 により０に正規化される”とき、Ｆ
1 がＦのグレブナ基底であることをチェックし、 ｆ）このチェックに失敗した場合、ａ）ｐをとり直して
ｂ）からｅ）を繰り返すことを特徴とするグレブナ基底
生成方法。 - 【請求項８】 請求項７において、前記（ｃ）のステッ
プは、多項式対の正規化形式を、ｐを法として計算し、
法ｐでの正規化形式が０でないと判断したときは、その
都度直ちに有理数上で正規化形式を計算することを特徴
とするグレブナ基底生成方法。 - 【請求項９】 請求項８において、有理数上で計算され
た正規化形式の頭係数を素数ｐで割り切れるか否かを判
定し、割り切れない場合のみ正規のグレブナ基底候補の
計算を続行するステップを有することを特徴とするグレ
ブナ基底生成方法。 - 【請求項１０】 請求項６から９において、対象となる
多項式集合Ｆを予め斉次化するステップと、 最終的に得られた多項式集合Ｆ1 を非斉次化するステッ
プとを備えたことを特徴とするグレブナ基底生成方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6255759A JPH07200538A (ja) | 1993-11-22 | 1994-10-20 | グレブナ基底生成方法及び装置 |
| US08/343,912 US5678055A (en) | 1993-11-22 | 1994-11-17 | Method and device for generating Grobner bases to reduce memory usage and increase computing speed |
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP29219493 | 1993-11-22 | ||
| JP5-292194 | 1993-11-22 | ||
| JP6255759A JPH07200538A (ja) | 1993-11-22 | 1994-10-20 | グレブナ基底生成方法及び装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH07200538A true JPH07200538A (ja) | 1995-08-04 |
Family
ID=26542400
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP6255759A Withdrawn JPH07200538A (ja) | 1993-11-22 | 1994-10-20 | グレブナ基底生成方法及び装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5678055A (ja) |
| JP (1) | JPH07200538A (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6035314A (en) * | 1996-07-17 | 2000-03-07 | Fujitsu Limited | Information processing method |
| FR2873875B1 (fr) * | 2004-07-28 | 2006-12-15 | Canon Kk | Localisation d'erreurs pour codes de geometrie algebrique |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3963905A (en) * | 1974-09-11 | 1976-06-15 | Bell Telephone Laboratories, Incorporated | Periodic sequence generators using ordinary arithmetic |
| US3971998A (en) * | 1975-05-02 | 1976-07-27 | Bell Telephone Laboratories, Incorporated | Recursive detector-oscillator circuit |
| US5142579A (en) * | 1991-01-29 | 1992-08-25 | Anderson Walter M | Public key cryptographic system and method |
| US5377207A (en) * | 1992-09-03 | 1994-12-27 | The United States Of America As Represented By The United States National Aeronautics And Space Administration | Mappings between codewords of two distinct (N,K) Reed-Solomon codes over GF (2J) |
| US5263085A (en) * | 1992-11-13 | 1993-11-16 | Yeda Research & Development Co. Ltd. | Fast signature scheme based on sequentially linearized equations |
-
1994
- 1994-10-20 JP JP6255759A patent/JPH07200538A/ja not_active Withdrawn
- 1994-11-17 US US08/343,912 patent/US5678055A/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US5678055A (en) | 1997-10-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Waki et al. | Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity | |
| Li et al. | Local correlation calculations using standard and renormalized coupled-cluster approaches | |
| JP7407291B2 (ja) | 浮動小数点数の乗算計算方法及び機器、並びに算術論理演算装置 | |
| CN1271508C (zh) | 产生具有可变精度的对数信号近似 | |
| Ikonen et al. | Componentwise splitting methods for pricing American options under stochastic volatility | |
| Estep et al. | An a posteriori–a priori analysis of multiscale operator splitting | |
| Gao et al. | Algorithm 846: MixedVol: a software package for mixed-volume computation | |
| Dou et al. | ENAP: An efficient number-aware pruning framework for design space exploration of approximate configurations | |
| US6631391B1 (en) | Parallel computer system and parallel computing method | |
| US10992314B2 (en) | Residue number systems and methods for arithmetic error detection and correction | |
| Mårtensson et al. | The number of the beast: Reducing additions in fast matrix multiplication algorithms for dimensions up to 666 | |
| CN113836386A (zh) | 一种并行模式搜索空间构造系统和方法 | |
| JPH07200538A (ja) | グレブナ基底生成方法及び装置 | |
| US20220414462A1 (en) | Computer-readable recording medium, information processing method, and information processing apparatus | |
| Griggio et al. | Efficient interpolant generation in satisfiability modulo linear integer arithmetic | |
| JP4202701B2 (ja) | 多項式剰余系演算装置、方法及びプログラム | |
| US20060123074A1 (en) | Representing Data Having Multi-dimensional Input Vectors and Corresponding Output Element by Piece-wise Polynomials | |
| US12566918B2 (en) | Document management system for adding appended information indicating changes made to the document to the revised document | |
| Brent | Further analysis of the Binary Euclidean algorithm | |
| JPH09134342A (ja) | グレブナ基底生成方法及び装置 | |
| Smith | A multiple-precision division algorithm | |
| Duff | MA57-a new code for the solution of sparse symmetric definite systems | |
| US6256656B1 (en) | Apparatus and method for extending computational precision of a computer system having a modular arithmetic processing unit | |
| JP4294000B2 (ja) | クロック遅延解析装置、クロック遅延解析方法、クロック遅延解析プログラム、および記録媒体 | |
| JP3164055B2 (ja) | 集積回路の遅延時間計算装置及び遅延時間計算プログラムを記録した記憶媒体 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20020115 |