Polyhedra and parallelization techniques

Polylib was developed while working on parallelization techniques, and its main users belong to this community. This is the reason why we give here more information on this domain. The iteration domain of a loop nest can be represented by a convex polyhedron, each integral point representing a vector of iteration indices. Therefore, operations on polyhedra are useful for doing loop transformations and other program restructuring transformations which are needed in parallelizing compilers. Along the same lines, polyhedra are a means of describing domain definitions of variables in systems of affine recurrence equations, a formalism introduced at the end of the sixties (of the last century!) to model parallel computations. Therefore the development of methods to do synthesis, analysis and verification of systems of recurrence equations requires also polyedra computations. By means of such methods one can transform an algorithm from a mathematical description into an equivalent form that can be implemented either with special purpose hardware (with systolic arrays for instance) or as a program which can be run on a multiprocessor system.