Study of innovative speeding-up of main-variables elimination of multivariate polynomial systems

多元多项式系统主变量消元创新加速研究

基本信息

批准号：
18K03389
负责人：
佐々木建昭
金额：
$ 1.83万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2018
资助国家：
日本
起止时间：
2018-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究の目的は，多変数多項式系の変数消去に関し，完璧だが計算が非常に重いグレブナー基底法に代る，実用的な算法を開発し有用性を示すことである。そのため，多変数多項式の再帰表現を用い，筆者が1992年に提案した『主項消去法』(二多項式系の主項同士を最小の乗数多項式で消去する)を採用した。算法は，具体的にはＧＣＤとＴＥＳ(Term Elimination Sequence)の計算の反復である。そして，前年度までに算法はほぼ完成の域に達した。●今年度(2022年度)は，第一に，算法そのものではなく，計算機内部での算法の実装方法を工夫した。ＴＥＳ計算に関しては，多項式の四則演算のみならず(再帰表現での)Ｍ簡約までも必要で，通常どおり実行したのでは随所で無駄な計算をすることになる。そこで，一つの指定された変数に関しては，その変数の指数部を指定された幅に収めて計算する多変数多項式算術を提案し，実装して有用性を確認した。●第二に，グレブナー基底算法では，主変数群が消去された終結式 R(u,v,..) が得られても，それと他の多項式たちとのＳ多項式を計算し続ける。すると，そのうちイデアルの最小元が計算される。同じことを二多項式系に対して主項消去を用いて行ったところ，予想だにしなかった見事な形で余計因子除去ができた。これは素晴らしい成果だと思う。●本研究で提案した変数消去法は種々の定理から成っている。それらの証明のミスを修正したり証明自体を抜本的に簡明化したりしながら，本研究全般に関する総合報告の形でまとめて，計算機代数に関するアメリカの専門誌(ACM Communications in Computer Algebra)に投稿した。昨年度末に論文受理の連絡を受けたが，その原稿自体の幾つかのミスを修正し，最新の成果もかなり書き込んだので，再審査に入っている。

这项研究的目的是开发实用的计算方法，以替代Grebner擦除多变量多项式系统变量的完美但极为重的基础方法，并证明其有用性。因此，我使用了作者在1992年提出的“主要术语消除方法”（消除了具有最小乘数多项式多项式多项式的二级化性系统的主要术语）。具体而言，计算是GCD和TES的计算（项消除序列）的迭代。到上一年，计算方法已经达到了几乎完成。 ●今年（2022），首先，我们设计了在计算机内实施计算的方法，而不是计算本身。关于TES计算，不仅需要多项式算术来简化M（在递归表达式中），而且如果正常执行，则无需进行不必要的计算。因此，对于一个指定的变量，我们提出了多变量的多项式算术，该多项式算术在指定的宽度中计算变量的指数部分，并实施它以确认其有用性。 ●其次，在Grebner基础计算中，即使获得了主要变量的终止方程R（U，V，..），也继续使用其他多项式来计算S多项式。然后计算理想的最小元素。当我使用二键型系统系统的主术语消除做同样的事情时，我能够以我从未想到的宏伟方式消除额外的因素。我认为这是一项伟大的成就。 ●本研究提出的可变消除方法包括各种定理。在纠正这些证据中的错误并从根本上简化了证明本身的情况下，这些证明是以一份有关这项研究的全面报告的形式编制的，并提交给计算机代数的美国杂志ACM通信。去年年底，我想接受该论文，但我纠正了手稿本身的一些错误，并且还写了很多最新结果，所以我正在审查中。