Add a generic symbolic polynomial class to support richer set of polynomial basis

[hongkai-dai]

Motivation

As discussed in #13602 , we would like to support a richer set of basis in polynomials. Namely our polynomial is written in the form of

p(x) = ∑ᵢ cᵢ ϕᵢ(x)

where ϕᵢ(x) is the basis, and cᵢ is the coefficient of the basis. We plan to support monomial basis, Chebyshev basis, and possibly Legendre basis. Each basis can be represented as a mapping from the variable to its degree.

Implementation

~PolynomialBasis~ PolynomialBasisElement

I plan to introduce a new abstract base class ~PolynomialBasis~ PolynomialBasisElement

class PolynomialBasisElement {
 private:
  std::map<Variable, int> var_to_degree_map_;
};

This base class represents an element of polynomial basis as a mapping from the variable to the degree. It also defines some common interfaces.

I will then derive ChebyshevBasisElement, MonomialBasisElement from PolynomialBasisElement class. The common operations include

• Multiplication, DerivedBasis * DerivedBasis. Note we will only support multiplication between the same type of basis. We won't allow multiplication between different basis (like multiply a ChebyshevBasisElement with a MonomialBasisElement).
• Differentiation.
• Integral.
• Evaluation.
• less_than (so PolynomialBasisElement can be used as a key in the map).

GenericPolynomial

I will introduce a new templated class to represent generic polynomial with a given basis

template <typename Basis>
class GenericPolynomial {
 private:
  std::map<Basis, symbolic::Expression> basis_to_coeff_map_;
};

And I will instantiate classes GenericPolynomial<MonomialBasisElement> and GenericPolynomial<ChebyshevBasisElement>.

To make the code compatible with the current codebase, I will add an alias using Polynomial = GenericPolynomial<MonomialBasisElement>, so that we can still use Polynomial class.

cc @TobiaMarcucci @soonho-tri what do you think?

[TobiaMarcucci]

I fully agree on the structure.

Regarding the name of the classes I'd like to share the thoughts I had when I was writing my python code. Initially I also used the names PolynomialBasis, MonomialBasis etc. However, the instances of these classes will be single elements of the basis of a GenericPolynomial, not the whole basis. For this reason I switched to PolynomialVector, MonomialVector etc, where vector here is in the algebraic sense (single element of a basis). Even if correct from a mathematical point of view, I still don't like this choice since the word vector can have many meanings and this is likely to cause a lot of misunderstandings. So I don't necessarily suggest to change name here, I just wanted to share my thought.

The name GenericPolynomial gives a sense of how this would differ from Polynomial, but I think that a more descriptive name might be better suited? However, also in this case I can't think of anything reasonably compact that explains that this is a linear combination of basis polynomials...

[SeanCurtis-TRI]

where vector here is in the algebraic sense (single element of a basis)

Surely a vector, in the algebraic sense, is a linear combination of space bases. Whether that's a Euclidian space or a function space. Its dimension is the size of the basis. So, a polynomial would be defined by a coefficient vector and a basis. I like the fact that the proposed design has the vector quantity (coefficients) and the basis (interpretation of the coefficients).

[TobiaMarcucci]

Just to clarify what I meant above. Say we have the vector space V of polynomials in n variables of degree d. Then we can pick a set of functions B = {phi_1, ..., phi_m} that span the whole V. Now, I think the correct wording would be to call the set B the "basis", and each of its elements phi_i a "basis vector". I think that calling the single element phi_i a "basis" is a little misleading. (I think this choice of words is also more common, see the first few lines here: https://en.wikipedia.org/wiki/Basis_(linear_algebra).)

In this sense I think that the name PolynomialBasisVector would be more rigorous than PolynomialBasis. Since the first clearly tells that this is going to be a single element phi_i of the basis, while with the second one might think that this class contains the whole set B.

[SeanCurtis-TRI]

@TobiaMarcucci I 100% agree with what you just wrote and apparently misunderstood what you'd written. I realize I'd misunderstood the semantics of the proposed design and can see that, as proposed, PolynomialBasis is a basis vector. :) And it would be a spanning set of those that form the basis.

[hongkai-dai]

@TobiaMarcucci I fully agree with you that PolynomialBasis is not a good name. As you said, a basis is a set {ϕ₁, ..., ϕₙ}, and the polynomial is written as p(x) = ∑ᵢ cᵢ ϕᵢ(x).

On the other hand, I am a bit hesitant to name it PolynomialBasisVector. The name vector is really overloaded, especially in C++. It is very likely later we will write an Eigen::Vector containing [ϕ₁, ..., ϕₙ], then we have an Eigen vector of PolynomialBasisVector, and the word "vector" appears for twice, with different meanings.

Since ϕᵢ is an "element" of the basis set {ϕ₁, ..., ϕₙ}, what do you think if we call ϕᵢ PolynomialBasisElement? I think it is pretty standard to refer to a member in a set as "element", described by wiki https://en.wikipedia.org/wiki/Element_(mathematics)

For the GenericPolynomial class, I chose this name for backward compatibility. We currently have Polynomial class in Drake, and it is used in many places. So I cannot call this new class Polynomial again. This new class is templated, since we often use the word "generic" to mean templated function/class in C++ (see https://www.geeksforgeeks.org/generics-in-c/), so I chose the name GenericPolynomial.

[avalenzu]

I agree that FooBasis should be reserved for classes that actually represent the full set functions. This is what math::BsplineBasis does. FWIW, in some of the method names of that class, we refer to the elements of the set as "basis functions." You could follow that here and call the class PolynomialBasisFunction. Of course, "function" is also an overloaded term ...

[TobiaMarcucci]

I see. Both options (PolynomialBasisElement and PolynomialBasisFunction) seem good choices to me. I agree that PolynomialBasisVector is not optimal. Regarding GenericPolynomial I didn't know that generic means templated, everything makes more sense now and I agree with this choice too.