Decompose a polynomial: find $f(x)$ such that $h(x) = f(g(x))$

Question

I try to make an algorithm that decomposes a polynomial, ie find $f(x)$ such that $h(x) = f(g(x))$ by knowing $h$ and $g$.

For example, having : $h(x) = 112x^6 + 1232x^5 + 2772x^4 - 3388x^3 + 847x^2 + 12$ and $g(x) = 4x^3 + 22x^2 - 11 x$ how to find $f$ ?

(for this example $f(x) = 7x^2+12$).

Answer 1

If

$$f(x) = \sum_{n} a_n x^n $$

then

$$ f(g(x)) = \sum_{n} a_n g(x)^n $$

so you just set the coefficients on $x$ equal in the equation

$$ h(x) = \sum_{n} a_n g(x)^n $$

and solve for the $a_n$. (hint: start with the highest degree terms)

Answer 2

If $f$ is to have degree $n$, take $n+1$ values $x_i$ such that $g(x_i)$ are distinct and use Lagrange interpolation on $f(g(x_i)) = h(x_i)$.

EDIT: If you don't know $g$, the problem is rather more interesting. Note that $g'$ is a factor of $h'$. If you can guess which of the roots of $h'$ are roots of $g'$, that determines $g$ up to a linear transformation (and you only need it up to that because you can adjust $f$). If $h$ has rational coefficients and you want $f$ and $g$ to have rational coefficients, the factorization of $h$ over the rationals can help.

In your example, $h' = 14 x (12 x^2 + 44 x - 11)(4 x^2 + 22 x - 11)$. If you guess $g' = 12 x^2 + 44 x - 11$, you get your $g$. If you guess $g' = 4 x^2 + 22 x - 11$, you get $g = \dfrac{4}{3} x^3 + 11 x^2 - 11 x$, and the result of the interpolation does not work.

Answer 3

Given just $h$, you know the degree of $g$ must divide that of $h$. For each given divisor of the degree of $h$, taken as degree of the desired $g$, you trivially find what the lead coefficients of $g,f$ must be -- if there is a decomposition of that degree at all, which there might not be. Then you find the next-to-lead coefficients of $g,f$ and so on -- if there is any decomposition with that degree.