Improve speed of symbolic::Polynomial::EvaluatePartial

[hongkai-dai]

trafficstars

Currently computing symbolic::Polynomial::EvaluatePartial is very slow. I have a mathematical program that takes 6 minutes to solve, but it takes 10 minutes to retrieve the solution when I use symbolic::Polynomial::EvaluatePartial.

Here is an example illustrating the issue.

1. I construct the polynomial as p(x) = m(x)ᵀ * S * m(x), where m(x) is a vector containing all my monomial basis, S is a matrix of decision variables.
2. I create a symbolic::Environment object that contains the value of S, set to S_val.
3. I call p(x).EvaluatePartial(env). This takes 10 minutes.
4. I tried the alternative approach to compute m(x)ᵀ * S_val * m(x), which gives me the same result as in step 3, but only takes 16 seconds.

I do expect step 3 to be slower than step 4, but I didn't expect that much slow.

I put my example in the branch https://github.com/hongkai-dai/drake/tree/benchmark_polynomial. You could see the comparison in bazel run common/symbolic/benchmarking:benchmark_polynomial.

[hongkai-dai]

Here is the callgrind result I see a lot of memory allocation and deallocation.

cc @jwnimmer-tri