Online Help

The following procedure computes the matrix multiplication $A=B·C$ :

MatrixMultiplication := proc (A, B, C, m, r, n)
local i, j, k;
for i to m do
for j to n do
for k to r do
A[i, j] := A[i, j] + B[i, k] * C[k, j]:
end do:
end do:
end do:
end proc:

Construct the ForLoop data structure from the procedure$\mathrm{MatrixMultiplication}$:

$\mathrm{loop}≔\mathrm{CreateLoop}\left(\mathrm{MatrixMultiplication}\right)\:$

Compute the dependence cone for all references to the ArrayA:

$\mathrm{dc1}≔\mathrm{DependenceCone}\left(\mathrm{loop}\,A\,\left[\mathrm{di}\,\mathrm{dj}\,\mathrm{dk}\right]\right)$

$\mathrm{dc1}≔\left[1\le \mathrm{dk}\,\mathrm{dj}=0\,\mathrm{di}=0\right]$

This result implies that the accesses to the array A with the indices $\left(i\,j\,k\right)$ are dependent on the previous writes to the array with indices $\left(i\,j\,k-n\right)$, where $n\in \mathbb{N}$. This means that accesses to A[i,j,k] depend on previous loop iterations that have the same $i$ and $j$ ($\mathrm{di}=0$ and $\mathrm{dj}=0$), but smaller values of $k$ ($1\le \mathrm{dk}$).

Consider the loop in a heat equation solving procedure:

heat_eq := proc (A, m, n)
local i, j;
for i to m do
for j to n do
A[i, j] := A[i-1, j-1] + 2 * A[i-1, j] + A[i-1, j+1] + 3:
end do
end do
end proc:
loop := CreateLoop(heat_eq):

Compute the dependence of A[i, j] with respect to A[i-1, j-1]:

$\mathrm{dc2}≔\mathrm{DependenceCone}\left(\mathrm{loop}\,A\left[i,j\right]\,A\left[i-1,j-1\right]\,\left[\mathrm{di}\,\mathrm{dj}\right]\right)$

$\mathrm{dc2}≔\left[\mathrm{dj}=1\,\mathrm{di}=1\right]$

Compute the dependence of A[i-1,j] with respect to A[i, j].

$\mathrm{dc3}≔\mathrm{DependenceCone}\left(\mathrm{loop}\,A\left[i-1,j\right]\,A\left[i,j\right]\,\left[\mathrm{di}\,\mathrm{dj}\right]\right)$

$\mathrm{dc3}≔\left[1\le 0\right]$

The result is an inconsistent system of equations (i.e. having no solution), meaning that there is no dependence of A[i-1,j] on A[i, j] in any previous iteration of the loop.