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.
