A Euclid style algorithm for MacMahon's partition analysis
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- scientific article; zbMATH DE number 1182831 (Why is no real title available?)
- scientific article; zbMATH DE number 1182907 (Why is no real title available?)
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- scientific article; zbMATH DE number 1391661 (Why is no real title available?)
- scientific article; zbMATH DE number 2209709 (Why is no real title available?)
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- A Primal Barvinok Algorithm Based on Irrational Decompositions
- A fast algorithm for MacMahon's partition analysis
- Algebraic invariants of five qubits
- Combinatorial reciprocity theorems
- Computing the Continuous Discretely
- Effective lattice point counting in rational convex polytopes
- Generalization of Stanley's monster reciprocity theorem
- Geometric algorithms and combinatorial optimization.
- Hard Equality Constrained Integer Knapsacks
- Invariants, Kronecker products, and combinatorics of some remarkable Diophantine systems
- MacMahon's partition analysis. VI: A new reduction algorithm
- MacMahon's partition analysis: The Omega package
- On Counting Lattice Points in Polyhedra
- On integer points in polyhedra
- Polynômes arithmétiques et méthode des polyedres en combinatoire
- The many aspects of counting lattice points in polytopes
Cited in
(10)- Completing the classification of representations of \(SL_n\) with complete intersection invariant ring
- On parity unimodality of \(q\)-Catalan polynomials
- A combinatorial approach to Frobenius numbers of some special sequences
- 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
- Polyhedral omega: a new algorithm for solving linear Diophantine systems
- The \(q, t\)-symmetry of the generalized \(q, t\)-Catalan number \(C_{(k_1,k_2,k_3)}(q,t)\)
- Generating functions for the quotients of numerical semigroups
- On magic distinct labellings of simple graphs
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)
