A Euclid style algorithm for MacMahon's partition analysis
A Euclid style algorithm for MacMahon's partition analysis
复制标题
DOI：
10.1016/j.jcta.2014.11.006
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
G. Xin
中科院分区：
文献类型：
--
作者：
G. Xin
Solutions to a linear Diophantine system, or lattice points in a rational convex polytope, are important concepts in algebraic combinatorics and computational geometry. The enumeration problem is fundamental and has been well studied, because it has many applications in various fields of mathematics. In algebraic combinatorics, MacMahon's partition analysis has become a general approach for linear Diophantine system related problems. Many algorithms have been developed, but “bottlenecks” always arise when dealing with complex problems. While in computational geometry, Barvinok's important result asserts the existence of a polynomial time algorithm when the dimension is fixed. However, the implementation by the LattE package of De Loera et al. does not perform well in many situations. By combining excellent ideas in the two fields, we generalize Barvinok's result by giving a polynomial time algorithm for MacMahon's partition analysis in a suitable condition. We also present an elementary Euclid style algorithm, which might not be polynomial but is easy to implement and performs well. As applications, we contribute the generating series for magic squares of order 6.
