2
$\begingroup$

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

enter image description here

Here is my handwork for $K=8$:enter image description here

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?

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – reuns Oct 9 at 14:27
  • $\begingroup$ @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? $\endgroup$ – Seyhmus Güngören Oct 9 at 14:49
  • $\begingroup$ @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. $\endgroup$ – Seyhmus Güngören Oct 9 at 15:01
  • $\begingroup$ $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$ ? $\endgroup$ – reuns Oct 9 at 15:10
  • 2
    $\begingroup$ 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? $\endgroup$ – user125932 Oct 9 at 18:21
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice answer. Thanks again. $\endgroup$ – Seyhmus Güngören Oct 10 at 21:47
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – Seyhmus Güngören Oct 9 at 17:06
  • $\begingroup$ I edited the question with some more material.. $\endgroup$ – Seyhmus Güngören Oct 9 at 17:24
  • $\begingroup$ @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. $\endgroup$ – Mike Earnest Oct 9 at 17:28
  • $\begingroup$ 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. $\endgroup$ – Seyhmus Güngören Oct 9 at 17:34
  • $\begingroup$ @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. $\endgroup$ – Mike Earnest Oct 9 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.