Polytope 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.

Nested loop programs are the typical, but not the only example, and the most common use of the model is for loop nest optimization in program optimization.

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.

An application of the polytope model, with the affine transformation

During the computation, each pixel's dithering error is collected by adding it back into the src array.

For the purposes of loop skewing, we can think of src[i][j] and dst[i][j] as the same element.)

We can then rewrite the code to loop on p and t instead of i and j, obtaining the following "skewed" routine.