Let $\mathbb{ K}[x_1, \dots, x_n]$ be a multivariate polynomial ring over a field $\mathbb{ K}$. Let $(u_1, \dots, u_n)$ be a sequence of $n$ algebraically independent elements in $\mathbb{ K}[x_1, \dots, x_n]$. Given a polynomial $f$ in $\mathbb{ K}[u_1, \dots, u_n]$, a subring of $\mathbb{ K}[x_1, \dots, x_n]$ generated by the $u_i$'s, we are interested infinding the unique polynomial $f_{ \rm new}$ in $\mathbb{ K}[e_1,\dots, e_n]$, where $e_1, \dots, e_n$ are new variables, such that $f_{ \mathrm{ new}}(u_1, \dots, u_n) = f(x_1, \dots, x_n)$. We provide an algorithm and analyze its arithmetic complexity to compute $f_{ \mathrm{ new}}$ knowing $f$ and $(u_1, \dots, u_n)$.
Categories: cs.SC