We first consider the base case of at most one outer sequential loop containing a number of perfectly nested loops. We assume that the local phase has analyzed and transformed the perfectly nested loops individually into canonical form. In section 6.4 we will discuss the general case of multiple nesting levels.
A collection of loops nests and arrays is represented as a bipartite
interference graph, 
.
The loop nests form one set of vertices 
,
and the arrays form the other set of vertices 
.
There is an undirected edge 
between an array and a loop nest if
the array is referenced in the loop nest.
Each edge contains one or more array index functions for all accesses of
the array in the loop nest.
Each connected component of the interference graph corresponds to a set of arrays and loop nests that have inter-related decompositions. The algorithms presented later in this section operate on a single connected component at a time.
To find a static decomposition, the following constraints are placed on the data and computation partitions.