Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.