The sets of non-linear functions we consider are MOD, DIV, FLOOR, and CEIL as well as step sizes other than one in the for-loops.

In a sequential program the ordering of the consecutive iterations is determined precisely. However this imposed ordering of the computations is only in part due to a data-relationship between different variables on different iteration instances, the so-called data dependency. Consecutive computations that lack a data dependency there fore can be executed in parallel.

A Single Assignment Program is a program in which every variable is assigned a value only once during the execution of the algorithm.

If we want to find all dependencies in a parameterized program, we could enumerate for all iterations, for the range of all parameters. Such a method, however, is highly inefficient and only suitable to solved very small problems. Finding the dependencies in an analytical way is the ultimate goal. Different methodologies exist, one technique is based upon Diophantine equations or Banerjee's inequalities. Another technique, the one we use, is based upon the Linear Programming methodology. Since we consider integer Linear Programming problems, which moreover are parameterized, we use the special class of Linear Program solutions, e.g. parametric integer programming (PIP). The MatParser tool uses the PIP technique as proposed and implemented by Feautrier.

P.Feautrier. Parameteric Integer Programming, Opérationelle; Operations Research, 20(3):243 268, 1988.

The original versions of MatParser (which was call HiPars) was build as a part of the HiFi framework developed at Delft University of Technology. This framework aimed to transform a high-level description of an algorithm into a parallel/pipelined chip-size application in a systematic way. It used, as it's high-level data-structure, Dependence Graphs (DGs). These DGs have a one-on-one relationship with the Single Assignment Programs. The HiPars tool extended the HiFi framework considerably by converting Matlab algorithms into a Single Assignment Program form and thus a DG description.

for i = 1 to 5 step 1
    [ A(i+2) ] = funcA( B(i+1) );
    [ B(i) ] = funcB( A(i) );
end

In this program, we see two functions, function funcA and function funcB, enclosed by one for-loop with iterator i. The function-calls are called a predetermined number of times. In this program, the functions are called 5 times in a sequential way. On every call, a value from the RHS is taken by the function funcA and function funcB, and a value is written back to the LHS. Variable A(i) and B(i+1) are read whereas variable A(i+2) and B(i) are written. We are interested whether or not a relation exists between the variables and the iterations.
If we assume that every variable occupies a piece of memory, a variable with the same name occupies the same memory location. From this, we conclude that variable A and B do not rely on each other. If there is a relation between variables, the variables must at least have identical names. Let us have closer look on the variable A and B at each iteration instance.

In the unrolled description we see that at iteration i=1, A(i+2) will write a value to element A(3) that is read by A(i) on iteration i=3. The same is true for iteration i=2 and i=3. In conclusion, there exists a relation between two instances of a variable at different iteration instance. Such a relation is called a data-dependency. Variable B has a data-relation, but here a value is read first and written later. At iteration i=1, variable B(i+1) reads value B(2) which is written by B(i) on iteration i=2.

A dependency defines a relation between variables at different iteration instances. Every statement and thus every variable have an iteration-vector. Due to the nature of the for-statements, these vectors are ordered in a specific way. The order of these vectors is called the lexicographical order. It means that iteration I is evaluated before iteration J.
Consider the following perfect nested loop program.

for i = 1 to 5 step 1
    for j = 1 to 5 step 1
        [a(i,j)] = func( a(i,j));
    end
end

In this program the iteration-vector I of the function-call func, is equal to (i,j). This iteration-vector receives all values between (1,1) and (5,5) in a specific order, as shown below.

If we start in point (1,1) the next point will be (1,2), until we reach the upper bound of iterator j in point (1,5). We move down a level which gives point (2,1). This continues until we reach point (5,5). This particular ordering is the lexicographical order.