کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655246 1632941 2015 29 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A Euclid style algorithm for MacMahon's partition analysis
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A Euclid style algorithm for MacMahon's partition analysis
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 131, April 2015, Pages 32-60
نویسندگان
,