The iteration-space traversal is a graphical representation of a traversal, using a grid of index vectors and dashed lines to indicate the traversal order. Determining data dependendies between scalar variables is easier than determining dependendies between non-scalar variables. Especially array references have subscripts that often refer to loop indices. The distance vector for a k-dimensional loop nest is an integer vector of length k that stores the distance between two index vectors for each dimension. The direction vector is an abstraction from the distance vector that captures the direction only, that is whether the distance is equal, greater, less.
Direction vectors are useful when there is no fixed distance.
The dependence level is a natural number that indicates the loop nest level for the loop that carries a data-dependence. Loop-independent dependendies are set to level infinity. The program dependence graph is a combination of the data dependence graph and the control-flow dependence graph. We haven' t covered the control-flow dependence graph, tough. The second loop, therefore, has no dependendies.