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 was wondering:

I'm desiring to compute the following polynomial, $X_1^2 + 2 X_1\cdot X_2 +X_2^2$ where $X_1,X_2$ are indeterminates. I can store intermediate results and use the binary operators of multiplication and addition on the indeterminates.

If the cost of taking a scalar multiple is $0$, and the cost of using addition and multiplication is $1$, then consider the following:

Let $P=X_1+X_2$ (cost $1$). Let $Q=P \cdot P$ (cost $1$).

Now at this point $Q$ is $(X1+X2) \cdot (X1+X2)$. Am I allowed to be done with the computation at this point? Or must I end with the explicit $X_1^2+ 2 X1 \cdot X2 +X_2^2$ in order to have computed $X_1^2+2X_1 \cdot X_2+ X_2^2$? (Which would take $5$ steps).

share|improve this question
    
I don't understand. You say you can use multiplication and addition "on the indeterminates". a) I'm not sure what that means, and b) in $Q=P\cdot P$ you're using multiplication on "$P$", by which you may be denoting either the result of performing $X_1+X_2$ or the polynomial $X_1+X_2$, neither of which is an indeterminate. The only way I can make sense of the first part of the question is if you in fact mean that you can perform multiplication and addition on the values taken by the indeterminates; but in that case $(X_1+X_2)\cdot(X_1+X_2)$ is the same as $X_1^2+2X_1\cdot X_2+X_2^2$. –  joriki Aug 23 '11 at 5:58
    
Sorry, I was a bit tired last night and couldn't find the answer to this anywhere. Anyways yes, I mean you can perform multiplication and addition on the values taken on by the indeterminates. And you answered my question. Thanks! –  seagaia Aug 23 '11 at 13:13
add comment

1 Answer

up vote 2 down vote accepted

Since you said my comment answered your question, I'm turning it into an answer so the question can be marked as answered:

If multiplication and addition refer to the values taken by the indeterminates, then $(X_1+X_2)\cdot(X_1+X_2)$ is the same as $X_1^2+2X_1\cdot X_2+X_2^2$, so there's nothing left to do; the computation was carried out efficiently with cost $2$ instead of cost $5$.

(By the way, under this interpretation of the question, presumably the coefficients of the polynomials are considered to be taken from some (relatively simple) subset of the possible values of the indeterminates? Else it wouldn't make sense to have scalar multiplication cost 0 and indeterminate multiplication cost 1, since they'd be the same operation.)

share|improve this answer
add comment

Your Answer

 
discard

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.