An implementation of MacMahon's partition analysis in ordering the number of lattice points in convex polyhedron with examples for systolic arrays

摘要

We have investigated the ldquoOmega calculusrdquo, as a computational method for solving problems via their corresponding Diophantine relation. These methods can be applied for the problems related with the number of lattice points in polyhedron, positively in our case for systolic array computations. From the corresponding systolic algorithm we form a system of linear diophantine equalities using the domain of computation which is given by the set of lattice points inside the polyhedron. Then we run the Mathematica program DiophantineGF.m. This program calculates the generating function from which is possible to find the number of solutions to the system of Diophantine equalities, which in fact gives the lower bound for the number of processors needed for the corresponding algorithm. There is given a mathematical explanation of the problem as well. We illustrate this for finding the lower bound of the systolic algorithm for discrete Fourier transformation (DFT).