In Mathematica, how do I compile the function Outer[] for an arbitrary number of arguments?

Question

If I want to find all possible sums from two lists list1 and list2, I use the Outer[] function with the specification of Plus as the combining operator:

In[1]= list1 = {a, b}; list2 = {c, d}; Outer[Plus, list1, list2]

Out[1]= {{a + c, a + d}, {b + c, b + d}}

If I want to be able to handle an arbitrary number of lists, say a list of lists,

In[2]= listOfLists={list1, list2};

then the only way I know how to find all possible sums is to use the Apply[] function (which has the short hand @@) along with Join:

In[3]= argumentsToPass=Join[{Plus},listOfLists]

Out[3]= {Plus, {a, b}, {c, d}}

In[4]= Outer @@ argumentsToPass

Out[4]= {{a + c, a + d}, {b + c, b + d}}

or simply

In[5]= Outer @@ Join[{Plus},listOfLists]

Out[5]= {{a + c, a + d}, {b + c, b + d}}

The problem comes when I try to compile:

In[6]= Compile[ ..... Outer @@ Join[{Plus},listOfLists] .... ]

Compile::cpapot: "Compilation of Outer@@Join[{Plus},listOfLists]] is not supported for the function argument Outer. The only function arguments supported are Times, Plus, or List. Evaluation will use the uncompiled function. "

The thing is, I am using a supported function, namely Plus. The problem seems to be solely with the Apply[] function. Because if I give it a fixed number of lists to outer-plus together, it works fine

In[7]= Compile[{{bob, _Integer, 1}, {joe, _Integer, 1}}, Outer[Plus, bob, joe]]

Out[7]= CompiledFunction[{bob, joe}, Outer[Plus, bob, joe],-CompiledCode-]

but as soon as I use Apply, it breaks

In[8]= Compile[{{bob, _Integer, 1}, {joe, _Integer, 1}}, Outer @@ Join[{Plus}, {bob, joe}]]

Out[8]= Compile::cpapot: "Compilation of Outer@@Join[{Plus},{bob,joe}] is not supported for the function argument Outer. The only function arguments supported are Times, Plus, or List. Evaluation will use the uncompiled function."

So my questions is: Is there a way to circumvent this error or, alternatively, a way to compute all possible sums of elements pulled from an arbitrary number of lists in a compiled function?

(Also, I'm not sure if "compilation" is an appropriate tag. Please advise.)

Thanks so much.

Answer 1

One way it to use With, to create a compiled function programmatically:

Clear[makeCompiled];
makeCompiled[lnum_Integer] :=
 With[{listNames = Table[Unique["list"], {lnum}]},
   With[{compileArgs = {#, _Integer, 1} & /@ listNames},
      Compile @@ Join[Hold[compileArgs],
        Replace[Hold[Outer[Plus, listNames]], 
          Hold[Outer[Plus, {x__}]] :> Hold[Outer[Plus, x]], {0}]]]];

It can probably be done prettier, but it works. For example:

In[22]:= p2 = makeCompiled[2]
Out[22]= CompiledFunction[{list13,list14},Outer[Plus,list13,list14],-CompiledCode-]

In[23]:= p2[{1,2,3},{4,5}]
Out[23]= {{5,6},{6,7},{7,8}}

In[24]:= p3 = makeCompiled[3]
Out[24]= CompiledFunction[{list15,list16,list17},Outer[Plus,list15,list16,list17],-CompiledCode-]

In[25]:= p3[{1,2},{3,4},{5,6}]
Out[25]= {{{9,10},{10,11}},{{10,11},{11,12}}}

HTH

Edit:

You can hide the compiled function behind another one, so that it is created at run-time and you don't actually see it:

In[33]:= 
Clear[computeSums]
computeSums[lists : {__?NumberQ} ..] := makeCompiled[Length[{lists}]][lists];

In[35]:= computeSums[{1, 2, 3}, {4, 5}]

Out[35]= {{5, 6}, {6, 7}, {7, 8}}

You face an overhead of compiling in this case, since you create then a compiled function afresh every time. You can fight this overhead rather elegantly with memoization, using Module variables for persistence, to localize your memoized definitions:

In[44]:= 
Clear[computeSumsMemoized];
Module[{compiled},
  compiled[n_] := compiled[n] = makeCompiled[n];
  computeSumsMemoized[lists : {__?NumberQ} ..] := compiled[Length[{lists}]][lists]];

In[46]:= computeSumsMemoized[{1, 2, 3}, {4, 5}]

Out[46]= {{5, 6}, {6, 7}, {7, 8}}

Answer 2

This is my first post. I hope I get this right.

If your inputs are lists of integers, I am skeptical of the value of compiling this function, at least in Mathematica 7.

For example:

f = Compile[{{a, _Integer, 1}, {b, _Integer, 1}, {c, _Integer, 1}, {d, _Integer, 1}, {e, _Integer, 1}}, 
        Outer[Plus, a, b, c, d, e]
    ];

a = RandomInteger[{1, 99}, #] & /@ {12, 32, 19, 17, 43};

Do[f @@ a, {50}] // Timing

Do[Outer[Plus, ##] & @@ a, {50}] // Timing

The two Timings are not significantly different for me, but of course this is only one sample. The point is merely that Outer is already fairly fast compared to the compiled version.

If you have reasons other than speed for compilation, you may find some use in Tuples instead of Outer, but you still have the constraint of compiled functions requiring tensor input.

f2 = Compile[{{array, _Integer, 2}}, 
      Plus @@@ Tuples@array
    ];

f2[{{1, 3, 7}, {13, 25, 41}}]

If your inputs are large, then a different approach may be in order. Given a list of lists of integers, this function will return the possible sums and the number of ways to get each sum:

f3 = CoefficientRules@Product[Sum[x^i, {i, p}], {p, #}] &;

f3[{{1, 3, 7}, {13, 25, 41}}]

This should prove to be far more memory efficient in many cases.

a2 = RandomInteger[{1, 999}, #] & /@ {50, 74, 55, 55, 90, 57, 47, 79, 87, 36};

f3[a2]; // Timing

MaxMemoryUsed[]

This took 3 seconds and minimal memory, but attempting the application of Outer to a2 terminated the kernel with "No more memory available."