Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 711
Jess Riedel Avatar asked Feb 11 '11 19:02

Jess Riedel


People also ask

What is a compiled function?

The compiled function expression also contains other information such as argument and result specifications, flags, error handlers, and version information. Since all of this information is stored in the expression, many of the tools for working with compiled functions can be written in the Wolfram Language.

What is module in Mathematica?

Module allows you to set up local variables with names that are local to the module. Module creates new symbols to represent each of its local variables every time it is called. Module creates a symbol with name xxx$nnn to represent a local variable with name xxx.


2 Answers

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}}
like image 124
Leonid Shifrin Avatar answered Oct 16 '22 02:10

Leonid Shifrin


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."

like image 31
Mr.Wizard Avatar answered Oct 16 '22 02:10

Mr.Wizard