Verification of the efficiency of the Grobner Basis for Various Combinatorial Problems

验证 Grobner 基对于各种组合问题的效率

• 批准号: 18540145
• 负责人: 渡辺 芳英
• 金额: $ 1.57万
• 依托单位: Doshisha University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18540145/
• 关键词: グレブナー基底; トーリックイデアル; 格子イデアル; 最尤復号; ネットワーク; 最大流問題; Conti-Traverso のアルゴリズム; ローレンスイデアル; マトロイド; サーキット; 整数計画法; グラフのネットワーク; ローレンス持ち上げ; RNA結合2次構造予測; 誤り訂正符号; 池上・楫アルゴリズム; BCH符号; グラフ上のネットワーク

1) 最尤復号の問題に付随する格子イデアルについて調べ, 符号が完全符号のときは, 復号に必要なイデアルの次数順序に関するグレブナー基底が, 最小重みの符号語だけで完全に決まることを示した.2) 最大流問題を整数計画問題として定式化し, 最大流問題に付随する整数計画問題の係数行列は縮小接続行列のローレンス持ち上げとして得られることから, 最大流問題に付随するトーリックイデアルの普遍グレブナー基底が, 有向グラフにおい辺の向きを無視した閉路に対応する2項式と辺の向きを無視した始点から終点への路に対応する2項式全体の和集合からなることを示した.

1）我们研究了与最大似然解码问题相关的格理想，并表明当代码是完整代码时，解码所需的理想度数的 Gröbner 基完全由具有最小权重的码字决定。 .2) 将最大流问题表述为整数规划问题，并且由于伴随最大流问题的整数规划问题的系数矩阵可以作为简化连接矩阵的劳伦斯升力获得，与最大流量问题相关的环面理想的通用 Gröbner 基可以表示为对应于有向图中的环的二项式，忽略边的方向，以及对应于从起点到终点的路径的二项式点，忽略边缘的方向，我们证明它由并集组成。

项目成果

2元線形符号の最尤復号におけるグレブナー基底を用いた方法-BCH符号への応用-

使用 Gröbner 基进行二进制线性码最大似然解码的方法 - BCH 码的应用 -

• 发表时间: 2007
• 作者: 渡邊芳英; 吉武純子; 池上大介
• 通讯作者: 池上大介

非線形方程式の解法による行列の特異値分解アルゴリズム

通过求解非线性方程的矩阵奇异值分解算法

• 发表时间: 2009
• 作者: 近藤弘一; 杉本昌平; 岩崎雅史
• 通讯作者: 岩崎雅史

整数計画法に基づくRNA間相互作用予測

基于整数规划的RNA-RNA相互作用预测

• 发表时间: 2007
• 作者: 市原慶太郎; 加藤有己; 渡邊芳英
• 通讯作者: 渡邊芳英

整数計画問題と2元線形符号の最尤復号

整数规划问题与二进制线性码的最大似然译码

• 发表时间: 2006
• 作者: 渡邊芳英

トーリックイデアルのグレブナー基底と最大流問題

环面理想和最大流量问题的 Gröbner 基础

• 发表时间: 2006
• 作者: 宮城奈津子; 渡邊芳英; 池上大介
• 通讯作者: 池上大介