Unimodular Transformation - Maple Help

Home : Support : Online Help : Programming : CodeTools : Program Analysis : Unimodular Transformation

CodeTools[ProgramAnalysis]

 UnimodularTransformation
 apply a unimodular transformation to a ForLoop

 Calling Sequence UnimodularTransformation(loop, M) UnimodularTransformation(loop, M, newvars)

Parameters

 loop - M - unimodular Matrix newvars - (optional) list of symbols, names for the index variables in the returned ForLoop

Description

 • This command applies a transformation to loop's index variables via the change of coordinates $\mathrm{newvars}=M·\mathrm{vars}$, where M is a unimodular matrix,  $\mathrm{vars}$ are the index variable(s) in loop, and $\mathrm{newvars}$ are the index variable(s) in the resulting transformed ForLoop.  The loop bounds and loop body in loop are updated according to this transformation.
 • The Matrix M is a square matrix with integer entries whose determinant is +1 or -1.  It must have the same number of rows and columns as there are elements in loop:-variables.
 • If the optional argument newvars is not supplied, the returned ForLoop will have the same names for its index variable(s) as the original loop, but with the transformation applied.  Otherwise, the returned loop's index variable(s) will have the names in newvars, ordered from the outermost to innermost loops.

Examples

 > $\mathrm{with}\left(\mathrm{CodeTools}\left[\mathrm{ProgramAnalysis}\right]\right):$

Create a ForLoop from the given procedure:

 > heateq := proc(A, m, n)     local i1, j1;     for i1 to m do         for j1 from i1 + 1 to n do             A[i1, j1] := A[i1 - 1, j1 - 1] + 2*A[i1 - 1, j1] + A[i1 - 1, j1 + 1] + 3:         end do:     end do: end proc;
 ${\mathrm{heateq}}{≔}{\mathbf{proc}}\left({A}{,}{m}{,}{n}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i1}}{,}{\mathrm{j1}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i1}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{m}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{j1}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i1}}{+}{1}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{n}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}{[}{\mathrm{i1}}{,}{\mathrm{j1}}{]}{≔}{A}{[}{\mathrm{i1}}{-}{1}{,}{\mathrm{j1}}{-}{1}{]}{+}{2}{*}{A}{[}{\mathrm{i1}}{-}{1}{,}{\mathrm{j1}}{]}{+}{A}{[}{\mathrm{i1}}{-}{1}{,}{\mathrm{j1}}{+}{1}{]}{+}{3}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (1)
 > $\mathrm{loop}≔\mathrm{CreateLoop}\left(\mathrm{heateq}\right):$

Create a unimodular matrix:

 > $U≔\mathrm{Matrix}\left(\left[\left[1,2\right],\left[2,3\right]\right]\right):$$\mathrm{LinearAlgebra}:-\mathrm{Determinant}\left(U\right)$
 ${-1}$ (2)

Apply a unimodular transformation to loop so that the returned loop has index variables named i2 and j2:

 > $\mathrm{transformed_loop}≔\mathrm{UnimodularTransformation}\left(\mathrm{loop},U,\left[\mathrm{i2},\mathrm{j2}\right]\right):$$\mathrm{GenerateProcedure}\left(\mathrm{transformed_loop}\right)$
 ${\mathbf{proc}}\left({A}{,}{m}{,}{n}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i2}}{,}{\mathrm{j2}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i2}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{5}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{min}}{}\left({2}{*}{n}{+}{m}{,}{3}{*}{n}{-}{1}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{j2}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{ceil}}{}\left({\mathrm{max}}{}\left({1}{/}{2}{+}{3}{/}{2}{*}{\mathrm{i2}}{,}{2}{*}{\mathrm{i2}}{-}{n}\right)\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{floor}}{}\left({\mathrm{min}}{}\left({3}{/}{2}{*}{\mathrm{i2}}{+}{1}{/}{2}{*}{m}{,}{5}{/}{3}{*}{\mathrm{i2}}{-}{1}{/}{3}\right)\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}{[}{−}{3}{*}{\mathrm{i2}}{+}{2}{*}{\mathrm{j2}}{,}{2}{*}{\mathrm{i2}}{-}{\mathrm{j2}}{]}{≔}{A}{[}{−}{1}{-}{3}{*}{\mathrm{i2}}{+}{2}{*}{\mathrm{j2}}{,}{2}{*}{\mathrm{i2}}{-}{\mathrm{j2}}{-}{1}{]}{+}{2}{*}{A}{[}{−}{1}{-}{3}{*}{\mathrm{i2}}{+}{2}{*}{\mathrm{j2}}{,}{2}{*}{\mathrm{i2}}{-}{\mathrm{j2}}{]}{+}{A}{[}{−}{1}{-}{3}{*}{\mathrm{i2}}{+}{2}{*}{\mathrm{j2}}{,}{2}{*}{\mathrm{i2}}{-}{\mathrm{j2}}{+}{1}{]}{+}{3}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (3)

The inverse transformation can be applied to generate a ForLoop that is equivalent to the original procedure $\mathrm{heateq}$ :

 > $\mathrm{transformed_back}≔\mathrm{UnimodularTransformation}\left(\mathrm{transformed_loop},{U}^{-1},\left[\mathrm{i1},\mathrm{j1}\right]\right):$
 > $\mathrm{GenerateProcedure}\left(\mathrm{transformed_back}\right)$
 ${\mathbf{proc}}\left({A}{,}{m}{,}{n}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i1}}{,}{\mathrm{j1}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i1}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{min}}{}\left({m}{,}{−}{1}{+}{n}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{j1}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i1}}{+}{1}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{n}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}{[}{\mathrm{i1}}{,}{\mathrm{j1}}{]}{≔}{A}{[}{\mathrm{i1}}{-}{1}{,}{\mathrm{j1}}{-}{1}{]}{+}{2}{*}{A}{[}{\mathrm{i1}}{-}{1}{,}{\mathrm{j1}}{]}{+}{A}{[}{\mathrm{i1}}{-}{1}{,}{\mathrm{j1}}{+}{1}{]}{+}{3}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (4)

The final procedure has a different upper bound on the outer loop than the original, but the two procedures are equivalent.

Compatibility

 • The CodeTools[ProgramAnalysis][UnimodularTransformation] command was introduced in Maple 2016.