A Euclid style algorithm for MacMahon's partition analysis
From MaRDI portal
Publication:482232
DOI10.1016/J.JCTA.2014.11.006zbMATH Open1305.05236arXiv1208.6074OpenAlexW1981750187MaRDI QIDQ482232FDOQ482232
Authors: Guoce Xin 
Publication date: 19 December 2014
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1208.6074
Recommendations
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)
Cites Work
- Effective lattice point counting in rational convex polytopes
- Title not available (Why is that?)
- MacMahon's partition analysis: The Omega package
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computing the Continuous Discretely
- The many aspects of counting lattice points in polytopes
- Geometric algorithms and combinatorial optimization.
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- Polynômes arithmétiques et méthode des polyedres en combinatoire
- Title not available (Why is that?)
- On integer points in polyhedra
- Title not available (Why is that?)
- A Primal Barvinok Algorithm Based on Irrational Decompositions
- A fast algorithm for MacMahon's partition analysis
- Algebraic invariants of five qubits
- Title not available (Why is that?)
- Title not available (Why is that?)
- Invariants, Kronecker products, and combinatorics of some remarkable Diophantine systems
- MacMahon's partition analysis. VI: A new reduction algorithm
- Generalization of Stanley's monster reciprocity theorem
- On Counting Lattice Points in Polyhedra
- Hard Equality Constrained Integer Knapsacks
- Combinatorial reciprocity theorems
Cited In (10)
- A combinatorial approach to Frobenius numbers of some special sequences
- Completing the classification of representations of \(SL_n\) with complete intersection invariant ring
- On parity unimodality of \(q\)-Catalan polynomials
- Algebraic combinatorics of diametric magic circles
- A fast algorithm for computing the number of magic series
- MacMahon partition analysis: a discrete approach to broken stick problems
- The \(q, t\)-symmetry of the generalized \(q, t\)-Catalan number \(C_{(k_1,k_2,k_3)}(q,t)\)
- Polyhedral omega: a new algorithm for solving linear Diophantine systems
- Generating functions for the quotients of numerical semigroups
- On magic distinct labellings of simple graphs
Uses Software
This page was built for publication: A Euclid style algorithm for MacMahon's partition analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482232)
