Univariate Polynomials in SymEngine

The Base

The superclass of all univariate polynomials is the UPolyBaseClass which is a CRTP. An end polynomial class has just two things, a Basic which is the generator of the said polynomial and a container, which contains the data of the polynomial (basically the degree, what is the coefficient of each monomial etc.).

The container needs to have operators overloaded for it to function as an internal for a polynomial. So, for Piranha we use piranha::polynomial as the container and for Flint we use the custom wrappers around fmpz_poly/fmpq_poly etc. For SymEngine we created a new template class ODictWrapper which is a wrapper around std::map. This wrapper implements all the operator overloads required, and maintains the data in the standard sparse polynomial representation.

The advantage of maintaining a standard set of overloads for the containers is that now, functions can be written as

template <typename Poly>
RCP<const Poly> mul_upoly(const Poly &a, const Poly &b)
{	
	// get_poly returns the internal container 
    auto dict = a.get_poly();
    dict *= b.get_poly();
    return Poly::from_container(a.get_var(), std::move(dict));
}

and be used by any univariate polynomial class.

The End Classes

Currently SymEngine has three types of polynomial classes for both integer and rational coefficient polynomials. They differ only in how their respective containers are implemented. So, we have UIntPoly and URatPoly as the SymEngine polynomials, UIntPolyFlint and URatPolyFlint as the Flint polynomials and finally, UIntPolyPiranha and URatPolyPiranha as the piranha polynomials. All of these can be used like any other symbolic inside SymEngine. Each of the three variants should behave identical to each other for an end user. The only difference is the internal container structure and implementation. It's a choice for the user depending on the type of polynomials and the manipulation they want to perform.

Each of these have the standard member functions get_coeff, get_var, get_degree, as_symbolic, get_lc, eval and multi_eval implemented. All of them also have a from_poly static function which maybe used to convert one polynomial type to another.

The common functionalities as of now for all of above mentioned polynomials are add_upoly, sub_upoly, mul_upoly, neg_upoly, divides_upoly. All of them also have ordered iterators implemented which can be used in the following way. They iterate over only the non-zero coefficients in the polynomial.

// x is a child of UPolyBase
for (auto it = x.obegin(); it != x.oend(); ++it) {
    auto coeff = it->second;
    auto power = it->first;
    ...
}

Apart from the above functions, both gcd_upoly and lcm_upoly are implemented for the Flint and Piranha versions of the SymEngine polynomials. These functions are yet to be implemented for the SymEngine variants.

We also have a UExprPoly class, which is the SymEngine implementation of polynomials with arbitrary expression coefficients. All the basic methods and manipulation functions work the exact same way for this class.

Currently, there are two main ways to construct a univariate polynomial. Poly::from_dict takes in a generator as well as a dictionary (map from monomial power to coefficient) and returns a RCP<const Poly>. Poly::from_vec takes in a generator as well and a vector (coefficient of each index) and returns a RCP<const Poly>. Another function from_container exists, which constructs polynomials given a generator and the underlying container directly (Ideally, this shouldn't be used by users)

The Structure

// the base
template <typename Container>
class UPolyBase : Basic

// super class for all non-expr polys, all methods which are
// common for all non-expr polys go here eg. degree, eval etc.
template <typename Cont, typename C>
class UNonExprPoly : UPolyBase<Cont>

// the specialized non-expr classes
template <typename D>
class UIntPolyBase : UNonExprPoly<D, integer_class>
// and
template <typename D>
class URatPolyBase : UNonExprPoly<D, rational_class>

// a specific implementation
// similar classes like UPiranhaPoly/UFlintPoly
template <typename D, template <typename X> class BaseType>
class USymEnginePoly : BaseType<D>

// end classes (few examples)
class UIntPoly : USymEnginePoly<UIntDict, UIntPolyBase>
class URatPoly : USymEnginePoly<URatDict, URatPolyBase>
class UIntPolyPir : UPiranhaPoly<piranha::poly, UIntPolyBase>
class URatPolyFlint : UFlintPoly<flint::poly, URatPolyBase>

What Remains

Right now, general purpose functions like add_upoly take in polynomials of the same type. They need to be generalized for all types of polynomials as arguments. This will involve converting one of the polynomials into the type of the other, and then using the already existing add_upoly function.

SymEngine polynomials require implementation of gcd and lcm. Also faster algorithmic techniques can be used for the multi_eval function.

Many helper functions can be added to help the end user like is_zero, is_one etc.