课题基金基金详情
MacMahon分拆分析在固定维数下的多项式时间算法
结题报告
批准号:
11171231
项目类别:
面上项目
资助金额:
45.0 万元
负责人:
辛国策
依托单位:
学科分类:
A0408.组合数学
结题年份:
2015
批准年份:
2011
项目状态:
已结题
项目参与者:
徐竞、梁志斌、杨洁、祝艳红、刘颖、班云飞
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
客服二维码
微信扫码咨询
中文摘要
本项目研究的MacMahon分拆分析是机械化算法的前沿课题,在组合学中有重要的应用,已成为处理线性丢番图方程组的非负整数解的一般性方法。目前已发展的快速算法解决了很多问题,但还没有适用于较大型计算的理想算法,因而发展快速稳定的算法是很有意义的。在计算几何领域,线性丢番图方程组的非负整数解被描述为有理凸多胞形内的格点,其计数问题作为数学中的一个基本问题,因其在很多数学研究中占有非常重要的地位,而被深入研究。重要的进展是Barvinok提出的在固定维数下的多项式时间算法,由Loera等发展的LattE软件包实现。虽然该算法是多项式时间算法,但在很多实际问题中的表现并不理想。通过有效结合两个领域中的优秀算法思想,我们将推广Barvinok的结果,实现MacMahon分拆分析在适当条件下的多项式时间算法,提供一个快速稳定的适用于较大型计算的MacMahon分拆分析软件包,有望建立一个经典算法。
英文摘要
线性丢番图方程的解,即有理凸多胞形的格点,是代数组合和计算几何中的重要概念。对应的计数问题是基础的,因具有广泛的应用而被深入研究。该领域中优秀算法有代数组合中 MacMahon 分拆分析方向的算法和计算几何中的 Barvinok 的多项式算法。这两种算法是互有优劣的完全不同的算法。为发展一个快速有效的算法来解决较大型问题,本项目结合了两个领域的优秀思想,拓展了Barvinok 的结果,给出了MacMahon 分拆分析在适当条件下的多项式算法。我们还给出了一个类欧氏的基础性算法,并编写了软件包 CTEuclid。利用该软件包,6阶幻方计数的公开问题得到了解决。.围绕主体课题,我们共完成了11项成果。我们在对称多项式理论中找到了重要的应用,特别是解决了代数组合学中著名的Shuffle 猜想的3个特例。我们完成了项目任务。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
DOI:--
发表时间:2015
期刊:Journal of Combinatorial Theory - Series A
影响因子:--
作者:Xin, Guoce;
通讯作者:
DOI:10.1137/120870025
发表时间:2014-01
期刊:SIAM J. Discret. Math.
影响因子:--
作者:Caiheng Li;Shaohui Sun;Jing Xu
通讯作者:Caiheng Li;Shaohui Sun;Jing Xu
DOI:10.1142/s0218196712500221
发表时间:2012-05
期刊:Int. J. Algebra Comput.
影响因子:--
作者:A. Garsia;N. Wallach;G. Xin;M. Zabrocki
通讯作者:A. Garsia;N. Wallach;G. Xin;M. Zabrocki
DOI:10.1112/plms/pds061
发表时间:2012-03
期刊:Proceedings of the London Mathematical Society
影响因子:1.8
作者:J. Coates;T. Dokchitser;Z. Liang;W. Stein;R. Sujatha
通讯作者:J. Coates;T. Dokchitser;Z. Liang;W. Stein;R. Sujatha
DOI:10.1016/j.jcta.2014.11.006
发表时间:2012-08
期刊:J. Comb. Theory A
影响因子:--
作者:G. Xin
通讯作者:G. Xin
Frobenius问题和denumerant的常数项方法
  • 批准号:
    --
  • 项目类别:
    面上项目
  • 资助金额:
    52万元
  • 批准年份:
    2020
  • 负责人:
    辛国策
  • 依托单位:
国内基金
海外基金