# Using Compile to speed up Function with PermutationProduct

I have the following fairly simple routine dot involving PermutationProduct that I wish to speed up using Compile or otherwise.

I am applying the Function simultaneously to large Lists of arguments

X={x1,x2,...}; Y={y1,y2,...}


using ParallelTable in the format

ParallelTable[dot[X[[i]], Y[[j]]], {i, Length[X]}, {j, Length[Y]}]


The Function is defined:

dot[x_, y_] := Block[
{l = Length[x]}, Cases[Select[#, ! (l < # <= 3 l) &] & /@
PermutationProduct[
Cycles[y + 2 l],
Cycles[Table[{2 l - i + 1, 2 l + i}, {i, l}]],
Cycles[x]
][[1]], Except[{}]]
/. Table[3 l + i -> i + l, {i, l}]]


The arguments x and y are Lists of the same Length consisting of partitions of the set {1,2,...,2n} into pairs where n is the Length of the arguments; and dot[x,y] is a List of the same form.

For example, where n == 4, the dot of elements

x = {{1, 2}, {3, 8}, {6, 5}, {4, 7}}
y = {{2, 3}, {5, 6}, {4, 1}, {8, 7}}


is

dot[x, y] == {{1, 2}, {3, 4}, {5, 6}, {7, 8}}


The order of the elements and subelements of x, y and dot[x,y] are irrelevant.

Any and all suggestions on improving the efficiency of this code will be enormously appreciated!

Thanks and regards,

Daniel

-
Cycles, PermutationProduct et al. are not compilable. The way out would be to rewrite these two functions in a procedural way, C-style and then you might have a better chance of being able to compile. – R. M. Sep 15 '12 at 16:02
This can probably be done with SparseArrays, which although not compilable may present some possibilities for optimization. Perhaps someone with more experience (than me) in this area of mathematics will be able to present an implementation in terms of permutation matrices. – Oleksandr R. Sep 15 '12 at 16:59