Felix Breuer, Zafeirakis Zafeirakopoulos,
"Polyhedral Omega: A New Algorithm for Solving Linear Diophantine Systems"
, Serie RISC Report Series, Nummer 15-09, RISC, RISC Hagenberg, 2015
Original Titel:
Polyhedral Omega: A New Algorithm for Solving Linear Diophantine Systems
Sprache des Titels:
Englisch
Original Kurzfassung:
Polyhedral Omega is a new algorithm for solving linear Diophantine systems (LDS), i.e., for computing a multivariate rational function representation of the set of all non-negative integer solutions to a system of linear equations and inequalities. Polyhedral Omega combines methods from partition analysis with methods from polyhedral geometry. In particular, we combine MacMahon's iterative approach based on the Omega operator and explicit formulas for its evaluation with geometric tools such as Brion decompositions and Barvinok's short rational function representations. In this way, we connect two recent branches of research that have so far remained separate, unified by the concept of symbolic cones which we introduce. The resulting LDS solver Polyhedral Omega is significantly faster than previous solvers based on partition analysis and it is competitive with state-of-the-art LDS solvers based on geometric methods. Most importantly, this synthesis of ideas makes Polyhedral Omega the simplest algorithm for solving linear Diophantine systems available to date. Moreover, we provide an illustrated geometric interpretation of partition analysis, with the aim of making ideas from both areas accessible to readers from a wide range of backgrounds.
Forschungs-