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

Question

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?

Answer 1

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.

Answer 2

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