I am wondering at a high level the mathematics of the Polyhedral Model.

The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of operations -- too large to be explicitly enumerated -- thereby requiring a compact representation. The polyhedral method treats each loop iteration within nested loops as lattice points inside mathematical objects called polyhedra, performs affine transformations or more general non-affine transformations such as tiling on the polytopes, and then converts the transformed polytopes into equivalent, but optimized (depending on targeted optimization goal), loop nests through polyhedra scanning.

I would like to understand the basic mathematical components of this but am having difficulty with the notation.

Specifically wondering what is going on in Figure 1 below. That is, where the polyhedra, lattice points, and affine transformations are, and how to represent/define them with mathematical notation. For instance, I haven't seen anything yet saying "a polyhedron from a loop is a tuple $p = (R, L, A)$ where $R$ is a set of loops, $L$ is a lattice and $A$ is a set of affine transformations, ...". Looking for the definitions of these 3 things and their relationship, as well as the relation between the loop variables and the what looks like is a matrix equation in the figure.

enter image description here

Figure (1) -^.

enter image description here

Figure (2) -^.

  • 1
    $\begingroup$ Try this: pdfs.semanticscholar.org/60c8/…. $\endgroup$ May 1, 2018 at 6:37
  • $\begingroup$ @YuvalFilmus thank you for that link, really good resource. The only thing left is understanding the matrices on page 5 section "2.3 The Source Polytope". Any help with that would be greatly appreciated. (similar to the matrices on the first diagram bottom left). Don't know where those numbers all come from. $\endgroup$
    – Lance
    May 2, 2018 at 6:22
  • 1
    $\begingroup$ I suggest reviewing linear algebra. $\endgroup$ May 2, 2018 at 6:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.