A large portion of deep learning research goes into convolution neural networks, hence there's a need for a fast algorithm. I wonder if an optimal convolution algorithm can be found symbolically with the power of MMA.

The goal is to reduce number of multiplications required to calculate the convolution of two lists. For example, in calculating the convolution of a list of length 4 with a list of length 3, the optimal algorithm would require only 4 multiplications based on equation 5 of this paper.

However, FullSimplify won't give the desired result. Here's my trivial (failed) attempt:

x = {x1, x2, x3, x4};
y = {y3, y2, y1};
z = FullSimplify@ListConvolve[y, x]

Which gives:

{x1 y1 + x2 y2 + x3 y3, x2 y1 + x3 y2 + x4 y3}.

The optimal result -based on the reference above- is

{(x1-x3)*y1 + (x2+x3)*(y1+y2+y3)/2 + (x3-x2)*(y1-y2+y3)/2, (x2+x3)*(y1+y2+y3)/2- (x2-x4)*y3 - (x3-x2)*(y1-y2+y3)/2}

Note that in the reference, division by 2 is not counted as a multiplication operation. I tried changing ComplexityFunction and did not yield anything useful. I suspect the problem is, the optimal algorithm would require use of intermediate variables (see equation (5) in the linked paper)

How do I discover the optimal (or at least somewhat optimized) algorithm automatically? I'm aware there may be ways to construct the optimal convolution algorithm given filter radius, however I'd like a more general solution.

  • $\begingroup$ What are you actually expecting as outcome? Note that the fourth and fifth line are pointless here. $\endgroup$
    – Feyre
    Commented Jan 30, 2017 at 10:16
  • 1
    $\begingroup$ @Feyre Expect equation (5) in the linked paper. The above code is an example of my failed attempt $\endgroup$
    – kh40tika
    Commented Jan 30, 2017 at 11:09
  • $\begingroup$ I don't think you can get an optimising algorithm from Mathematica. You can construct it yourself, but it's barely faster even with huge arrays than the built in function, so there's really no reason for Mathematica to provide it. $\endgroup$
    – Feyre
    Commented Jan 30, 2017 at 14:50
  • $\begingroup$ Seems like this might be amenable to genetic programming methods, but...it would take some real work to cast in that framework. $\endgroup$ Commented Jan 30, 2017 at 15:09
  • $\begingroup$ @Feyre The point is to use MMA to find a symbolic representation of an optimal algorithm, then maybe write a custom C / CUDA code generator. There are a lot cases of convolution like cyclic, lattice, ... and I'd like a automated way to derive fast algorithm $\endgroup$
    – kh40tika
    Commented Jan 30, 2017 at 15:10


Browse other questions tagged or ask your own question.