Algorithms and Parallel Computing

10.4 DERIVING THE DEPENDENCE GRAPH FOR AN ALGORITHM

We use Eq. 10.1 to study the dependence of the algorithm variables. Variable y is an output variable, and variables x and a are input variables. We note that the algorithm gives rise to a 2-D graph since we have two indices, i and j. Since the dimensionality of is low, it is best to visualize using a dependence graph since this is easier for humans to analyze. We refer to any point in as a vector p

(10.2)

For given values of the indices, the vector corresponds to a point in the space.The graph covers the points p(i, j) ∈ where the range of the indices defines the boundaries of as

(10.3)

Note that extends to ∞ in the i direction, ...