2
$\begingroup$

Suppose that I have two polynomials with a degree of $n$, $A(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ and $B(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_0$ and the coefficients of these polynomials are zero or greater. Suppose I multiply $A(X)$ and $B(x)$, $C(x) = A(x)B(x)$.

For the polynomial $C(x)$, how do I determine if the term $c_i$ is zero or greater? What is the fastest algorithm for determining whether for all terms $c_i$ if it is zero or nonzero?

$\endgroup$
  • $\begingroup$ I m sorry, I am slow and do not get your question. If $A$ and $B$ have positive coefficients, then so does $C$... What are you not telling me? $\endgroup$ – András Bátkai Dec 3 '18 at 6:38
  • $\begingroup$ $A(x)$ and $B(x)$ only consists of coefficients that are either zero and greater than zero. For example, let $A(x) = x^ 2$ and $B(x) = x^2 + 1$. As a result, $A(x) B(x) = x^4 + x^2 + 1$. We notice from this result that the coefficents that are zero are terms $x^3$ and $x$. I was wondering if there is there is a fast polynomial, possibly faster than $O(nlogn)$, to compute the coefficients that would be zero. $\endgroup$ – mtber75 Dec 3 '18 at 6:50
  • 1
    $\begingroup$ Well, there is an obvious linear-time ($O(i)$) algorithm: $c_i=0$ if and only if for each $j\le i$, $a_j=0$ or $b_{i-j}=0$. Since the answer depends on all these coefficients, you have at least to read them, hence you cannot make it significantly faster. $\endgroup$ – Emil Jeřábek Dec 3 '18 at 8:00
  • $\begingroup$ It may be easier to write the question as follows: let $A, B$ be finite sets of nonnegative integers; is there a fast way to determine $C = \{a + b|a \in A, b \in B\}$? This is equivalent, by making $A$ the set of nonzero coefficients of $A(x)$, and similarly for $B,C$. $\endgroup$ – user44191 Dec 3 '18 at 8:00
  • 1
    $\begingroup$ @EmilJeřábek I think mtber75 is looking for an algorithm to cover all of the $c_i$ at once, not one at a time. In that case, the naive algorithm takes $O(n^2)$ $\endgroup$ – user44191 Dec 3 '18 at 8:04
1
$\begingroup$

Since polynomial multiplication is essentially (non-cyclic) convolution, and for arbitrary polynomials $A(x),B(x)$, the fastest known convolution algorithms (based on the fast fourier transform) have complexity $O(d \log d)$ where $d=\max\{\deg A,\deg B\},$ without assumptions on the structure of the zero coefficients of $A$ and $B,$ there can't be a faster algorithm without any breakthroughs in algorithms computing convolutions.

Edit: In the light of the comments, I now realize that it is correct one does not need to compute the full convolution. Modeling the nonzero coefficients of $A,B$ as subsets $S_A,S_B,$ of $\{1,\ldots,d\}$ the question can be related to computing properties of the sumset $S_A+S_B\subset \{1,2,\ldots,2d\}.$

It seems to me that in general this can be done in time $w_A w_B$ in the worst case where $w_A=\# S_A,$ is the weight (no. of nonzero coefficients) of the polynomial or the cardinality of $S_A,$ etc. So certainly, if $w_A w_B <d \log d,$ this would give an improvement.

If the specific coefficient was $c_i,$ and we were only interested in whether $c_i$ was zero, then one would only need to consider the sets $S_A \cap \{0,1,2,\ldots,c_i\}$ and $S_b \cap \{0,1,2,\ldots c_i\}$ and by scanning forward in one and backward in the other set, while looking for two terms which sum to $c_i,$ one could actually determine if $c_i$ was nonzero or not in $O(c_i)$ time.

$\endgroup$
  • $\begingroup$ But you are not actually computing the convolution. $\endgroup$ – Emil Jeřábek Dec 3 '18 at 8:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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