Once the partition and number of virtual processor dimensions have been found, the algorithm finds the orientations. The partitions determine the kernels of each of the decomposition matrices. Since the orientations in a connected component of the interference graph are all relative to one another, we can choose one arbitrary decomposition matrix and derive the rest of the decomposition matrices in the component. The algorithm starts by choosing an data decomposition matrix for an array x of dimension m such that the nullspace of is the data partition . According to Eqn. 3, the computation decomposition matrix for a loop nest j that references the array is . Again, for simplicity of presentation we assume that the array index functions are invertible. The data decomposition matrix, , for another array y accessed in the same loop nest is calculated using . The remaining decompositions in the connected component are calculated in a similar fashion. When an array index function only accesses a subsection of the array (i.e. ), auxiliary variables are used temporarily in the unspecified dimensions of the data decomposition matrix. Note that when calculating the orientations, non-integer entries in the decomposition matrices can result. Because orientations are relative, the matrices can be multiplied by the least common multiple to eliminate the fractions.
Proof:We only outline the proof here because of space considerations. We prove this lemma by induction. The base case is the array x for which we chose an arbitrary decomposition matrix that has the specified kernel. Using partition constraints 2 and 3, we then show that as each decomposition matrix is calculated, it has the correct nullspace and holds.
Proof:This theorem follows directly from Lemmas 4.2 and 4.3.