How many convolutions are necessary for all possible $K-1$-fold convolutions of $K$ vectors?

There are $$K$$ vectors and all possible $$K-1$$-fold convolutions are needed to be determined. How many minimum number of convolutions are necessary?

Here is an example:

Lets assume we have $$K=4$$. Then we have four vectors $$v_1$$, $$v_2$$, $$v_3$$, $$v_4$$ and the followings are to be computed:

$$1.$$ $$v_1\star v_2\star v_3$$ here we need $$2$$ convolutions

$$2.$$ $$v_1\star v_2\star v_4$$ here we need $$1$$ convolution because we already have $$v_1\star v_2$$ from the previous step

$$3.$$ $$v_3\star v_4\star v_1$$ here we need $$2$$ convolutions

$$4.$$ $$v_3\star v_4\star v_2$$ here we need $$1$$ convolution because we already have $$v_3\star v_4$$ from the previous step.

Altogether one needs $$6$$ convolutions which is normally $$8$$, if we do not use the convolutions already done in the previous steps.

If we use the same idea for $$K=5$$

$$1.$$ $$v_1\star v_2\star v_3\star v_4$$ here we need $$3$$ convolutions

$$2.$$ $$v_1\star v_2\star v_3\star v_5$$ here we need $$1$$ convolution

$$3.$$ $$v_1\star v_2\star v_4\star v_5$$ here we need $$2$$ convolutions

$$4.$$ $$v_5\star v_4\star v_3\star v_1$$ here we need $$3$$ convolutions

$$5.$$ $$v_5\star v_4\star v_3\star v_2$$ here we need $$1$$ convolutions

Altogether one needs $$10$$ convolutions which is normally $$15$$, if we do not use the convolutions already done in the previous steps.

For $$K=6$$ one can reduce $$24$$ convolutions to $$14$$ and for $$K=7$$ instead of $$35$$ convolutions one only needs to calcule $$19$$ (added: it is actually $$18$$ according to my new calculation) convolutions if I am not mistaken.

Here are the questions:

Question $$1$$: I am wondering for a possible generalization to this. For example if we have $$K=1000$$ or $$K=1000000$$? How many minimum number of convolutions are necessary?

I can also find all $$K-1$$ convolutions by first convolving all $$K$$ vectors with each other resulting in say vector $$v$$. Then I go ahead with deconvolving $$v$$ with $$v_1$$, then deconvolving $$v$$ with $$v_2$$, etc.

In this way, I need to make only $$999$$ convolutions and $$1000$$ deconvolutions. However the size of devonvolutions is much bigger than the size of convolutions. For example if the length of $$v_1$$ is $$10$$, then all convolutions are between vectors of size $$1\times 10$$. However, if we use the deconvolution idea, the deconvoltion will be beween a vector of size $$10$$ and size $$9001$$ for $$K=1000$$. Moreover, deconvolution is not always reliable.

Question $$2$$: which idea is the best to obtain $$K-1$$-fold convoltions with less number of computations for example if one wants to implement using a computer program?

Here is the figure that I got from my examples above. The y axis is the ratio of the minimum that I found by my hands to the clairvoyent so $$K(K-2)$$. It is almost linear but it wont be like that forever.. Here is my handwork for $$K=8$$: So accroding to my examples, the answer should be $$4K-10$$, which is surprisingly linear. If true, it is also very interesting because for large $$K$$, one needs to have a very good strategy to achieve the minimum number of convolutions.. what should be the strategy? how can one prove it, if correct?

• Convolution is the same as product. You want to find how many multiplications are needed to compute $f(K-1,K)$ the set of all products of $K-1$ distinct elements from a given set with $K$ elements. What I can say is that we need $2^K-K-1$ multiplications to compute $F(K)=\bigcup_{n=0}^K f(n,K)$ : proof every time we do a multiplication we have computed at most one new element in $F(K)$ and there are $2^K$ elements in $F(K)$ and $K+1$ of them are given. The obvious algorithm (putting an order and computing the least elements first) needs $2^K-K-1$ multiplications to compute $F(K)$. – reuns Oct 9 at 14:27
• @reuns Sorry but no. For $K=1000$, a clairvoyent way of handling this problem requires 1 million convolutions. Simply 999 convolutions for each case. Since there are 1000 cases, we have almost 1 millon convolutions. According to what you wrote we need about $2^{1000}$. It is impossible. I think 1 million is still too many. Because a clever way will probably need some $10000$s according to my best guess. And the question: what is this clever way and how many? – Seyhmus Güngören Oct 9 at 14:49
• @reuns Okey, and what does it then say for $K=1000$? could you please also make comments on the given examples in the question? The complexity is definitely not exponential. – Seyhmus Güngören Oct 9 at 15:01
• $f(n,K)$ contains ${K \choose n}$ elements while $F(K)$ contains $2^K$ elements. Why would you want to look specifically at $f(K-1,K)$ ? How do you prove that the complexity is polynomial in $K$ ? – reuns Oct 9 at 15:10
• What is convolution here? Is it commutative? I don't understand the pattern in the order of convolutions given in your examples. Could you not just compute $a_1 = v_1$, $a_2 = a_1 \star v_2, \dots, a_{K-1} = a_{K-2} \star v_{K-1}$, and $b_1 = v_K$, $b_2 = v_{K-1} \star b_1, \dots, b_{K-1} = v_2 \star b_{K-2}$, so the desired convolutions are $a_{K-1}, a_{K-2} \star b_1, \dots, a_1 \star b_{K-2}, b_{K-1}$ with a total of $3(K-2)$ convolutions? – user125932 Oct 9 at 18:21

To expand a bit on my comment, here's an approach that uses only $$3K-6$$ convolutions -- I'm not sure that it's optimal, but it's near optimal in the sense that at least $$\approx 2K$$ convolutions are necessary.

First compute the $$2K-2$$ vectors \begin{align*} a_1 &= v_1 & b_1 &= v_K\\ a_2 &= a_1 \star v_2 = v_1 \star v_2 & b_2 &= v_{K-1} \star b_1 = v_{K-1} \star v_K\\ a_3 &= a_2 \star v_3 = v_1 \star v_2 \star v_3 & b_3 &= v_{K-2} \star b_2 = v_{K-2} \star v_{K-1} \star v_K\\ &\vdots &&\vdots\\ a_{K-1} &= a_{K-2} \star v_{K-1} = v_1 \star v_2 \star \cdots \star v_{K-1} & b_{K-1} &= v_2 \star b_{K-2} = v_2 \star v_3 \star \cdots \star v_k \end{align*} (so generally for $$2 \leq i \leq K-1$$, $$a_i := a_{i-1} \star v_i$$ and $$b_i := v_{K+1-i} \star b_{i-1}$$), using $$2(K-2)$$ convolutions.

The desired $$(K-1)$$-fold convolutions are $$a_{K-1}, a_{K-2} \star b_1, a_{K-3} \star b_2, \dots, a_1 \star b_{K-2}, b_{K-1}$$. Each of these $$K$$ except for the first and last uses an additional convolution, giving a total of $$3K-6$$ convolutions.

• Nice answer. Thanks again. – Seyhmus Güngören Oct 10 at 21:47

Yes, there is a faster way. Instead of taking $$K^2$$ convolutions, it can be done in $$O(K\log K)$$ convolutions. I will refer to $$v_1\star \dots \star v_{i-1}\star v_{i+1}\star\dots v_K$$ as a "deficient convolution" of $$\{v_1,v_2,\dots,v_K\}$$. You want to compute all deficient convolutions.

The base cases of the algorithm are when $$K=1,2,3$$. In the firs two cases, zero convolutions are needed, and for $$K=3$$, three convolutions are required. From now on, assume $$K\ge 4$$.

Split $$v_1,\dots,v_K$$ into two sets $$A$$ and $$B$$ with $$\lfloor K/2\rfloor$$ and $$\lceil K/2\rceil$$ vectors. Recursively compute all of the deficient convolutions of $$A$$ and $$B$$. Furthermore, compute the convolution of all elements in $$A$$, call it $$v_A$$, and similarly compute $$v_B$$. Finally, compute the convolution of $$v_A$$ with all the deficient convolutions for $$B$$, then the convolution of $$v_B$$ with all deficient convolutions for $$A$$. Combined, these make all deficient convolutions for $$A\cup B=\{v_1,v_2,\dots,v_K\}$$.

Assuming for the moment that $$K=2^k$$ is a power of two, the number of convolutions required can be computed exactly as \begin{align} (2^k+2)+2(2^{k-1}+2)+4(2^{k-2}+2)+\dots+2^{k-2}(2^2+2) &=(k-1)2^k+2\cdot (2^{k-1}-1)\\ &\le K\log_2 K+2K\\ &\in O(K\log K) \end{align} Furthermore, since it can be easy shown by induction that the number of convolutions required grows monotonically in $$K$$. Therefore, the bound for powers of two extends to all values of $$K$$ (perhaps with an additional constant factor of two).

• I think I found the answer although I have no proof for that. The answer is $4K-10$. You can see that this result is true for all given examples. Plus I did also for $8$ by hands and it is indeed $22$! It is really surprising that for $K=10^6$ one needs only around $4$ million convolutions.. – Seyhmus Güngören Oct 9 at 17:06
• I edited the question with some more material.. – Seyhmus Güngören Oct 9 at 17:24
• @SeyhmusGüngören Be careful with extrapolating trends which are only supported by a couple small numbers. I see no reason to believe $4K-10$ is achievable in general. – Mike Earnest Oct 9 at 17:28
• It is just true for $K=4,5,6,7,8$ and I can try it for $9$. if I find $26$, will you believe that it is possible? your result is fairly off for all examples. For example for $K=8$ your exact result it $38$ but the best result is $22$. This alone says that there should be somethin better. – Seyhmus Güngören Oct 9 at 17:34
• @SeyhmusGüngören I had small mistake in computation of the exact number of steps, stemming from a wrong base case. My method indeed achieves $22$ convolutions when $K=8$, and furthermore agrees with your results for $K=3,4,5,6,7$. However, when $K=9$ I get $27$ convolutions instead of $26$. Let us see if you can do better. – Mike Earnest Oct 9 at 18:01