Скачать или смотреть Linear Dioph. Systems, Integer Partitions, Polyhedra and Applications, part 2/2 - Z. Zafeirakopoulos

This is the second part of Zafeirakis Zafeirakopoulos (Gebze Technical University) talk given in GANT seminar about "Linear Diophantine Systems, Integer Partitions, Polyhedra and Applications".

Abstract: Polyhedral Omega is an algorithm for solving linear Diophantine systems, 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. It 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. This synthesis of ideas makes Polyhedral Omega by far the simplest algorithm for solving linear Diophantine systems available to date.

After presenting the algorithm, we will see some applications in number theory and computer science. Finally, we will discuss how to generalize Polyhedral Omega, in order to solve families of problems parametrized by some integer parameter.