2
$\begingroup$

I want to substitute a variable with a number in multivariate polynomials. For example for the polynomial

$ P = (z^2+yz^3)x^2 + zx $

I want to substitute $z$ with $3$.

I have intuition how to do that algorithmatic: I have to regard the coefficients in $F[y,z]$ and make a recursive call of that method to obtain even more coeffcients in $F[z]$, substitute them and return the result to the "lower" recursiv calls. Is that a good idea? I'm not really interested in the formulation a real algorithm but more in the complexity of the substitution operation.

I think that the above sketched algorithm can be bound with $\mathcal{O}(\deg_x(P)\deg_y(P)\deg_z(P))$. Is that correct? The bound is not really strict. Any ideas for a stricter bound?

Our is there a faster algorithm which is used in practice? And what is its complexity?

1 Answers 1

1

There are classical results (Ostrowski) on optimality of Horner's method and related evaluation schemes. These have been improved by Pan, Strassen and others. Searching on "algebraic complexity" with said authors should quickly locate pertinent literature.

  • 0
    @joachim See e.g. this [article](http://www.mathunion.org/ICM/ICM1974.2/Main/icm1974.2.0497.0502.ocr.pdf) [V. Strassen, "Some results in algebraic complexity theory", *Proceedings of the International Congress of Mathematicians Vancouver* (1974) 497-501] and references therein.2017-09-29