Suppose $p(x)$ is a polynomial of degree $n$. Suppose $q(x)$ is a polynomial of degree $\lfloor n/k \rfloor$. Is there an efficient way of calculating $p(x) * q(x^k)$? Let's assume that multiplying any two coefficients is $O(1)$.
Observe that $q(x^k)$ is a polynomial of degree at most $n$, and all terms but those at position which is a multiple of $k$ are zero.
I am looking for a way of exploiting the fact that $q(x^k)$ is sparse, and more over, not just randomly sparse, but sparse with a regular distance of $k$.
I am aware of generic polynomial multiplication algorithms such as those based on FFT that run in $O(n \ log \ n)$, but applying this directly makes no use of the above properties. Is something like $O(n + \frac{n}{k} log \frac{n}{k})$ achievable?
Let the cost of polynomial multiplication be $f(n)$, where the unit is the time of an addition. Then you can see $p$ as the sum of $k$ polynomials of $n/k$ terms, taking every $k^{th}$ terms. You can perform $k$ independent multiplies, taking $kf(n/k)$ operations in total, and regroup the results, requiring $k(2n/k)$ additions.
Ignoring overhead, the total cost is $kf(n/k)+2n$. To obtain a net gain, you need to have
$$kf\left(\frac nk\right)+2n<f(n).$$
With $f(n)=an\log n$,
$$an\log\left(\frac nk\right)+2n<an\log n$$ for $$\log k>\frac2a.$$