symbolic::Polynomial vs. ::Polynomial is confusing, inconvenient

[ggould-tri]

(This extracts as a new issue the confusion mentioned in https://github.com/RobotLocomotion/drake/issues/6219#issuecomment-305580534 of #6219) (This relates to #4460 and #4911) (This relates to the conversation at https://drakedevelopers.slack.com/conversation/C0JNB2E3S/p1512747658000059 )

Right now we have two different Polynomial classes; the older one is used mostly for PiecewisePolynomial and its related Trajectory. The newer one is Symbolic and is used in Systems. The new version can be converted to the old version but not vice versa.

This is untidy and confusing of course. It is also inconvenient if you are writing a System that needs to do computation on a Trajectory.

Probably the whole PiecewisePolynomialTrajectory ecosystem should be reconsidered in light of Symbolic?

[soonho-tri]

My plan is to templatize the existing symbolic::Polynomial so that we can specify the type of coefficient as drake::Polynomial does. For the current use cases, we can instantiate it with symbolic::Expression as the type of coefficient (in Sums-of-squares setup, for example). To replace the existing drake::Polynomiald, we can instantiate it with double so that we can achieve a comparable performance.

[RussTedrake]

Related to this, I found it surprising that Expression::ToPolynomial returns a Polynomiald (not symbolic::Polynomial). Could we add a bread-crumb in the documentation of that method to tell people they can convert to symbolic::Polynomial using the symbolic::Polynomial constructor?

[soonho-tri]

@RussTedrake to remind you of this issue. Let me check things and get back to you. Please feel free to share your thoughts here as well.

[RussTedrake]

I would love to see them merge. I do think we need to be careful to not have a setback in performance, as some of our core tools for planning depend on the trajectory classes which depend on this.

[jwnimmer-tri]

Setting aside any decisions about which conversion operators to support, how the trajectory classes work, which class we prefer to use in practice (e.g., #10839), or whether we eventually want to combine the multiple implementations into one ...

As a starting point, I'd like to immediately rename one or both of the two classes (drake::Polynomial and/or drake::symbolic::Polynomial) to use a different class name. Having two classes with the same name that differ only by namespace is pretty confusing.

We could probably leave the Polynomiald and VectorXPoly typedef names unchanged, thought renaming those as well for consistency might still help.

Does anyone have suggestions for a new name for one or the other Polynomial?

Trying to think about names, I looked into how the two classes differ. Other than runtime performance (which will vary over time, to the point of not being distinguishable down the road) it seems like the only major differences are:

(1) A drake::Polynomial<T> allows for any type of monomial coefficient, e.g., an AutoDiffXd. The symbolic::Polynomial only supports Expression coefficients.

(2) A symbolic::Polynomial allows for proper string names for its terms' variables (via symbolic::Variable). The drake::Polynomial<T> only supports uint32_t nonces as variables. (In theory, it can encrypt 4-letter names into the integer, but in practice only a tiny bit of unit test code in Drake uses this feature and it's not bound in pydrake.)

Thinking about new names for drake::Polynomial<T>, I came up with: (a) SpotPoly to highlight it's ancestry; (b) AnonPoly to highlight that it doesn't name its variables; (c) FlatPoly to highlight that the representation is simple std::vector without any indexed lookups, etc. (d) GradPoly to highlight that it supports autodiff for its coefficients.

Any better suggestions?

[RussTedrake]

How about symbolic::Polynomial => symbolic::PolynomialExpression?

[hongkai-dai]

Inside drake::Polynomial and symbolic::Polynomial, they use the same word Monomial and Term, but mean different things, which is very confusing.

1. Monomial in symbolic::Polynomial means indeterminates raised up to certain degrees. In drake::Polynomial it means the product of the coefficient and the indeterminates raised to certain degrees. So a Monomial in symbolic::Polynomial looks like x²y³, but in drake::Polynomial looks like 2x²y³.
2. Term in symbolic::Polynomial means the product of a coefficient with the indeterminates raised to certain degrees. In drake::Polynomial it means raising a single indeterminate to a certain degree. So Term in symbolic::Polynomial look like 2x²y³, but in drake::Polynomial looks like x².

I would say the symbolic::Polynomial's definition of Monomial and Term is more standard. For example here is wiki's definition of Term. On the other hand monomial has two definitions in wiki. It could mean either x²y³ or 2x²y³, and I often use the one in the optimization community as described by monomial

[hongkai-dai]

@jwnimmer-tri apart from renaming the class, what is your plan to combine symbolic::Polynomial and drake::Polynomial? I plan to add more support in MathematicalProgram which uses a polynomial whose coefficients are just double. So for the moment I can use drake::Polynomial but it becomes very confusing when we also use symbolic::Polynomial (for sum-of-squares optimization) also in MathematicalProgram class.

[jwnimmer-tri]

I don't have specific plans. I was hoping to find a way to get rid of drake::Polynomial (starting by renaming it to be something less confusing). My money is on symbolic::Polynomial being the right answer long term.

Would it help if we added ExpressionKind::AutoDiff as another cell type? It would be like ExpressionKind::Constant, but would allow for partial derivatives to follow along.

[hongkai-dai]

Thanks Jeremy!

Renaming drake::Polynomial can work.

I am not entirely sure if symbolic::Polynomial is the right answer long term. There is a special type of polynomial, that all the coefficients are just constant, instead of symbolic::Expression. Namely the polynomial is in the form of 2xy + 3y², but not 2a*xy + 3b * y² with the coefficients 2a and 3b. This type of polynomial will be used extensively in "polynomial optimization problem" (POP), as mentioned in #19908 .

We could add a is_coefficient_constant method in symbolic::Polynomial class to check if all the coefficients are constant, do you think this is the best approach?

[jwnimmer-tri]

Renaming drake::Polynomial can work.

I interpreted Russ's comment upthread as a disagreement with such a rename.

We could add a is_coefficient_constant method in symbolic::Polynomial class to check if all the coefficients are constant, do you think this is the best approach?

Are you saying we need a faster implementation than decision_variables().empty()?

[jwnimmer-tri]

From f2f with @hongkai-dai -- action item for me: create a WIP branch of what it might look like to get rid of drake::Polynomial entirely (keeping symbolic::Polynomial), while maintaining the current capabilities (e.g., PiecewisePolynomial<AutoDiffXd>) and sufficient speed. Then we can discuss whether it meets all goals, or what other questions remain. From that WIP + discussion, we can create a project plan to make the transition.

The ETA for a WIP should be soonish, but the transition might be longer (6+ months) and will certainly be pretty gradual (not deprecating anything right away).

[jwnimmer-tri]

BTW The two implementations differ in what "degree" means. With x²y³ the drake::Polynomial says the "degree" is 6 (the product of the exponents), but symbolic::Polynomial says the "total degree" is 5 (the sum of the exponents).

https://en.wikipedia.org/wiki/Monomial#Degree is pretty clear that summation is correct. I haven't been able to find any citation that multiplies the powers.

The spotless implementation seems to use the sum, not the product, too: https://github.com/spot-toolbox/spotless/blob/4b128416858d32ca1a094780325133b9f2cb8753/%40msspoly/deg.m#L4

The "product" has been Drake's implementation since forever (aka 09da6c188f4, in 2015).

To date, we only seem to use it for "empty" checks (zero degree vs non-zero degree), or for univariate polynomials, so it's mostly moot. If we ever started to do even/odd checks on multivariate polynomials, we would probably have noticed earlier.