For the methods that the omega test uses, we must able to determine which loops and conditionals control the execution of each statement. The omega test can produce exact dependence information for any single structure procedure in which the expression in the subscripts, loop bounds and conditionals are affine functions of the loop indices and loop independent variables, and the loop steps are know constants. A dependence relation is a mapping from one iteration space to another, and is represented by a set of linear constraints on variables that represent the value of the loop indices at the source and sink of dependence and the value of the symbolic constant. The notation which The omega test uses :
refers to the vector of loop
variables
a specific value of a
vector of loop variables referred to as iteration vector
a specific array reference function in a program
, the set of iteration vectors for which 
or 
is executed
F(j) is executes before F(k)
Informally, there is a definition-use
pair between a definition and a use of the
same array variable A, if and only if 
reads
the value that was written by 
.
This occurs when 
access first the same
memory element as 
, and there is no
intervening write (kill write) by and redefinition to this memory
element.
Formally, there is a definition-use pair between 
and
iff the following (dependence) formula can
be satisfied (there exists 
and 
for which the formula is true).
The loop bound and conditional expressions that contain loops are
affine function of loop variable. Array reference functions for one
dimensional subset of affine function referred to as restricted affine
(RA) functions of loop variable.
By definition an RA function 
where 
, and 
is the scalar
product.
Example of RA functions are: 
. Example of non-RA
functions is 2x+3y+1.
This representation is selected since practical array reference
functions are usually RA functions, and RA functions make it possible
to use integer programming for definition-use analysis without any restriction.
Within this domain the dependence formulae lead to Presburger
formulas.
Unfortunately, even in simple cases the formula to be evaluated is
difficult as following example:
for i=1 to 2*n do
a[i] = .... d
for j=0 to n-1 do
a[2*j] = ..... r1
a[2*j+1]= ..... r2
endfor
.... = a[i] u
endfor
The formula that corresponds to the definition-use
problems in above example is as
follows:
The first part of this formula describe the constraints for
definition-use
without
any redefinition, the other part express the effect of 
and 
,
respectively.
The omega test takes this inequalities and constrains and turn the
data dependence problem as a integer problem . Then solve this integer
programming by using these inequalities and then the solution is
taken as the exact data dependence information for array in side these
loop.