Algorithms for combinatorial problems based on commutative algebra

基于交换代数的组合问题算法

• 批准号: 23500025
• 负责人: SATO Yosuke
• 金额: $ 1.83万
• 依托单位: Tokyo University of Science
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500025/
• 关键词: ブーリアン・グレブナー基底; 組み合わせ問題; 数独問題の難易度; ブーリアン・グレブナー基 底

We investigated a theory of commutative algebra that is needed for a solution algorithm for combinatorial problems. We have concentrated on problems which do not essentially contain integer arithmetic. As a result, we found that our algorithm based on Boolean Groebner bases methods is the best method.We also implemented our method on the computer algebra system Risa/Asir and showed the efficiency of our algorithm, especially our algorithm is more practical on the environment of parallel computations.

我们研究了一个理论的交换代数，这是需要一个解决算法的组合问题。我们已经集中在基本上不包含整数算术的问题。结果表明，基于Groebner基方法的算法是最优的，并在计算机代数系统Risa/Asir上实现了该算法，证明了该算法的有效性，特别是在并行计算环境下更具有实用性。

项目成果

Complex QE について

关于复杂量化宽松

• 发表时间: 2013
• 作者: 深作亮也;井上秀太郎;佐藤洋祐
• 通讯作者: 佐藤洋祐

Boolean Groebner Bases

布尔 Groebner 基

• 发表时间: 2011
• 期刊: Journal of Symbolic Computation
• 影响因子: 0.7
• 作者: Yosuke Sato;Shutaro Inoue;Akira Suzuki;Katsusuke Nabeshima & Ko Sakai
• 通讯作者: Katsusuke Nabeshima & Ko Sakai

Stability of Groebner Bases in Terms of a Commutative von Neumann Regular Ring

交换冯·诺依曼正则环上格罗布纳基的稳定性

• 发表时间: 2012
• 作者: Qian-Ping Gu;Hisao Tamaki;Yosuke Sato
• 通讯作者: Yosuke Sato

Boolean Gröbner Bases

布尔格罗布纳基

• 发表时间: 2011
• 期刊: Journal of Symbolic Computation
• 影响因子: 0.7
• 作者: Yosuke Sato;Shutaro Inoue;Akira Suzuki;Katsusuke Nabeshima and Ko Sakai
• 通讯作者: Katsusuke Nabeshima and Ko Sakai

Maple等の数式処理システムを支える計算機代数アルゴリズム

支持Maple等数学公式处理系统的计算机代数算法

• 发表时间: 2012
• 作者: Yuichi Futa;Noboru Endou;Yasunari Shidama;佐藤 洋祐
• 通讯作者: 佐藤 洋祐