Let $$P:\mathbb{R}^n\to\mathbb{R}^n$$ be a vector valued polynomial. What is the computational complexity of the composition of two such polynomial? Can the Fast Fourier Transform be employed on vector valued polynomial?
Composition of single valued polynomials can be computed using FFT, as by this answer.