Efficiency issue of partial multimonomial expansion in `semipolynomial_form`

[bowenszhu]

When input is, for example, expr = (x + 1)^5 and degree = 2, pow_of_add together with partial_multinomial_expansion is able to efficiently partially expand the exponentiation ^5 of the addition x + 1 and outputs

Symbolics.BoundedDegreeMonomial(x^2, 10, false) + Symbolics.BoundedDegreeMonomial(x, 5, false) + 1

as the terms that are within the degree upper bound and

Symbolics.BoundedDegreeMonomial(1, (1 + x)^5, true) + Symbolics.BoundedDegreeMonomial(1, -1, true) + Symbolics.BoundedDegreeMonomial(1, -10(x^2), true) + Symbolics.BoundedDegreeMonomial(1, -5x, true)

as the terms whose power exceeds degree, which works well.

However, for a bit more complex expression, for example expr = ((x + 1)^4 + x)^3 with degree = 2, partial_multinomial_expansion causes many extra terms in the intermediate stage of Postwalk(RestartedChain(rules)).

        ^
       / \
      +   3
     / \
    ^   x
   / \
  +   4
 / \
x   1

As the term rewriter follows post-order traversal scheme, the subtree (x + 1)^4 is partially expanded to

Symbolics.BoundedDegreeMonomial(x^2, 6, false), Symbolics.BoundedDegreeMonomial(x, 4, false), 1, Symbolics.BoundedDegreeMonomial(1, (1 + x)^4, true), Symbolics.BoundedDegreeMonomial(1, -1, true), Symbolics.BoundedDegreeMonomial(1, -6(x^2), true), Symbolics.BoundedDegreeMonomial(1, -4x, true)

which consists of $2 \times (\textrm{degree} + 1) + 1 = 2 \times (2 + 1) + 1 = 7$ terms and they are sent to the ^ operation in the root node in the expression tree to be further partially expanded. However, the full expansion of (x + 1)^4 includes only $4 + 1 = 5$ terms.

Therefore, partial expansion may cause extra burden for operations in the ancestor nodes in the expression tree.

[bowenszhu]

And the current implementation as of v4.10.3 seems to always assume that the input expr contains only positive integer exponent.