 CGAL 5.4 - Polynomial
PolynomialTraits_d Concept Reference

## Definition

A model of PolynomialTraits_d is associated with a type Polynomial_d. The type Polynomial_d represents a multivariate polynomial. The number of variables is denoted as the dimension $$d$$ of the polynomial, it is arbitrary but fixed for a certain model of this concept. Note that univariate polynomials are not excluded by this concept. In this case $$d$$ is just set to one.

PolynomialTraits_d provides two different views on the multivariate polynomial.

• The recursive view: In this view, the polynomial is considered as an element of $$R[x_0,\dots,x_{d-2}][x_{d-1}]$$. That is, the polynomial is treated as a univariate polynomial over the ring $$R[x_0,\dots,x_{d-2}]$$.
• The symmetric or multivariate view: This view is symmetric with respect to all variables, considering the polynomial as an element of $$R [x_0,\dots,x_{d-1}]$$.

Many functors consider the polynomial as a univariate polynomial in one variable. By default this is the outermost variable $$x_{d-1}$$. However, in general it is possible to select a certain variable.

Refines:
AlgebraicStructureTraits
Polynomial_d
Has Models:
CGAL::Polynomial_traits_d<Polynomial_d>

## Concepts

conceptCanonicalize
For a given polynomial $$p$$ this AdaptableUnaryFunction computes the unique representative of the set

${\cal P} := \{ q\ |\ \lambda * q = p\ for\ some\ \lambda \in R \},$

where $$R$$ is the base of the polynomial ring. More...

conceptCompare
This AdaptableBinaryFunction compares two polynomials, with respect to the lexicographic order with preference to the outermost variable. More...

conceptConstructCoefficientConstIteratorRange
This AdaptableUnaryFunction returns a const iterator range over the coefficients of the given polynomial, with respect to the outermost variable, $$x_{d-1}$$. The range starts with the coefficient for $$x_{d-1}^0$$. More...

conceptConstructInnermostCoefficientConstIteratorRange
This AdaptableUnaryFunction returns a const iterator range over all innermost coefficients of the given polynomial. More...

conceptConstructPolynomial
This AdaptableFunctor provides several operators to construct objects of type PolynomialTraits_d::Polynomial_d. More...

conceptDegree
This AdaptableUnaryFunction computes the degree of a PolynomialTraits_d::Polynomial_d with respect to a certain variable. More...

conceptDegreeVector
For a given PolynomialTraits_d::Polynomial_d $$p$$ this AdaptableUnaryFunction returns the degree vector, that is, it returns the exponent vector of the monomial of highest order in $$p$$, where the monomial order is the lexicographic order giving outer variables a higher priority. In particular, this is the monomial that belongs to the innermost leading coefficient of $$p$$. More...

conceptDifferentiate
This AdaptableUnaryFunction computes the derivative of a PolynomialTraits_d::Polynomial_d with respect to one variable. More...

conceptEvaluate
This AdaptableBinaryFunction evaluates PolynomialTraits_d::Polynomial_d with respect to one variable. More...

conceptEvaluateHomogeneous
This AdaptableFunctor provides evaluation of a PolynomialTraits_d::Polynomial_d interpreted as a homogeneous polynomial in one variable. More...

conceptGcdUpToConstantFactor
This AdaptableBinaryFunction computes the $$gcd$$ up to a constant factor (utcf) of two polynomials of type PolynomialTraits_d::Polynomial_d. More...

conceptGetCoefficient
This AdaptableBinaryFunction provides access to coefficients of a PolynomialTraits_d::Polynomial_d. More...

conceptGetInnermostCoefficient
For the given PolynomialTraits_d::Polynomial_d this AdaptableBinaryFunction returns the coefficient of the (multivariate) monomial specified by the given CGAL::Exponent_vector. More...

This AdaptableUnaryFunction computes the innermost leading coefficient of a PolynomialTraits_d::Polynomial_d $$p$$. The innermost leading coefficient is recursively defined as the innermost leading coefficient of the leading coefficient of $$p$$. In case $$p$$ is univariate it coincides with the leading coefficient. More...

conceptIntegralDivisionUpToConstantFactor
This AdaptableBinaryFunction computes the integral division of two polynomials of type PolynomialTraits_d::Polynomial_d up to a constant factor (utcf) . More...

conceptInvert
This AdaptableUnaryFunction inverts one variable in a given PolynomialTraits_d::Polynomial_d, that is, for a given polynomial $$p$$ it computes $$x^{degree(p)}p(1/x)$$. More...

conceptIsSquareFree
This AdaptableUnaryFunction computes whether the given a polynomial of type PolynomialTraits_d::Polynomial_d is square free. More...

conceptIsZeroAt
This AdaptableFunctor returns whether a PolynomialTraits_d::Polynomial_d $$p$$ is zero at a given Cartesian point, which is represented as an iterator range. More...

conceptIsZeroAtHomogeneous
This AdaptableFunctor returns whether a PolynomialTraits_d::Polynomial_d $$p$$ is zero at a given homogeneous point, which is given by an iterator range. More...

This AdaptableUnaryFunction computes the leading coefficient of a PolynomialTraits_d::Polynomial_d. More...

conceptMakeSquareFree
This AdaptableUnaryFunction computes the square-free part of a polynomial of type PolynomialTraits_d::Polynomial_d up to a constant factor. More...

conceptMonomialRepresentation
This Functor outputs the monomial representation of the given polynomial, that is, it writes all non zero terms of the polynomial as std::pair<CGAL::Exponent_vector, PolynomialTraits_d::Innermost_coefficient_type> into the given output iterator. More...

conceptMove
This AdaptableFunctor moves a variable at position $$i$$ to a new position $$j$$. The relative order of the other variables is preserved, that is, the variables between $$x_i$$ and $$x_j$$ (including $$x_j$$) are moved by one position while $$x_i$$ is moved to the former position of $$x_j$$. More...

conceptMultivariateContent
This AdaptableUnaryFunction computes the content of a PolynomialTraits_d::Polynomial_d with respect to the symmetric view on the polynomial, that is, it computes the gcd of all innermost coefficients. More...

conceptNegate
This AdaptableUnaryFunction computes $$p(-x)$$ for a given polynomial $$p$$. More...

conceptPermute
This AdaptableFunctor permutes the variables of the given polynomial with respect to a permutation $$\sigma$$, that is, each monomial $$\prod x_i^{e_i}$$ will be mapped to the monomial $$\prod x_{\sigma(i)}^{e_i}$$. The permutation $$\sigma$$ is given by the iterator range of length PolynomialTraits_d::d, which is supposed to contain the second row of the permutation. More...

conceptPolynomialSubresultants
Computes the polynomial subresultant of two polynomials $$p$$ and $$q$$ of type PolynomialTraits_d::Polynomial_d with respect to outermost variable. Let $$p=\ccSum{i=0,\ldots,n}{} p_i x^i$$ and $$q=\ccSum{i=0,\ldots,m}{} q_i x^i$$, where $$x$$ is the outermost variable. The $$i$$-th subresultant (with $$i=0,\ldots,\min\{n,m\}$$) is defined by. More...

conceptPolynomialSubresultantsWithCofactors
Computes the polynomial subresultant of two polynomials $$p$$ and $$q$$ of degree $$n$$ and $$m$$, respectively, as defined in the documentation of PolynomialTraits_d::PolynomialSubresultants. Moreover, for $$\mathrm{Sres}_i(p,q)$$, polynomials $$u_i$$ and $$v_i$$ with $$\deg u_i\leq m-i-1$$ and $$\deg v_i\leq n-i-1$$ are computed such that $$\mathrm{Sres}_i(p,q)=u_i p + v_i q$$. $$u_i$$ and $$v_i$$ are called the cofactors of $$\mathrm{Sres}_i(p,q)$$. More...

conceptPrincipalSturmHabichtSequence
Computes the principal leading coefficients of the Sturm-Habicht sequence of a polynomials $$f$$ of type PolynomialTraits_d::Polynomial_d with respect a certain variable $$x_i$$. This means that for the $$j$$-th Sturm-Habicht polynomial, this methods returns the coefficient of $$x_i^j$$. More...

conceptPrincipalSubresultants
Computes the principal subresultant of two polynomials $$p$$ and $$q$$ of type PolynomialTraits_d::Coefficient_type with respect to the outermost variable. The $$i$$-th principal subresultant, $$\mathrm{sres}_i(p,q)$$, is defined as the coefficient at $$t^i$$ of the $$i$$-th polynomial subresultant $$\mathrm{Sres}_i(p,q)$$. Thus, it is either the leading coefficient of $$\mathrm{Sres}_i$$, or zero in the case where its degree is below $$i$$. More...

conceptPseudoDivision
This AdaptableFunctor computes the pseudo division of two polynomials $$f$$ and $$g$$. More...

conceptPseudoDivisionQuotient
This AdaptableBinaryFunction computes the quotient of the pseudo division of two polynomials $$f$$ and $$g$$. More...

conceptPseudoDivisionRemainder
This AdaptableBinaryFunction computes the remainder of the pseudo division of two polynomials $$f$$ and $$g$$. More...

conceptResultant
This AdaptableBinaryFunction computes the resultant of two polynomials $$f$$ and $$g$$ of type PolynomialTraits_d::Polynomial_d with respect to a certain variable. More...

conceptScale
Given a constant $$c$$ this AdaptableBinaryFunction scales a PolynomialTraits_d::Polynomial_d $$p$$ with respect to one variable, that is, it computes $$p(c\cdot x)$$. More...

conceptScaleHomogeneous
Given a numerator $$a$$ and a denominator $$b$$ this AdaptableFunctor scales a PolynomialTraits_d::Polynomial_d $$p$$ with respect to one variable, that is, it computes $$b^{degree(p)}\cdot p(a/b\cdot x)$$. More...

conceptShift
This AdaptableBinaryFunction multiplies a PolynomialTraits_d::Polynomial_d by the given power of the specified variable. More...

conceptSignAt
This AdaptableFunctor returns the sign of a PolynomialTraits_d::Polynomial_d $$p$$ at given Cartesian point represented as an iterator range. More...

conceptSignAtHomogeneous
This AdaptableFunctor returns the sign of a PolynomialTraits_d::Polynomial_d $$p$$ at a given homogeneous point, which is given by an iterator range. More...

conceptSquareFreeFactorize
This Functor computes a square-free factorization of a PolynomialTraits_d::Polynomial_d. More...

conceptSquareFreeFactorizeUpToConstantFactor
This AdaptableFunctor computes a square-free factorization up to a constant factor (utcf) of a PolynomialTraits_d::Polynomial_d. More...

conceptSturmHabichtSequence
Computes the Sturm-Habicht sequence (aka the signed subresultant sequence) of a polynomial $$f$$ of type PolynomialTraits_d::Polynomial_d with respect to a certain variable $$x_i$$. The Sturm-Habicht sequence is similar to the polynomial subresultant sequence of $$f$$ and its derivative $$f':=\frac{\partial f}{\partial x_i}$$ with respect to $$x_i$$. The implementation is based on the following definition: More...

conceptSturmHabichtSequenceWithCofactors
Computes the Sturm-Habicht polynomials of a polynomial $$f$$ of degree $$n$$, as defined in the documentation of PolynomialTraits_d::SturmHabichtSequence. Moreover, for $$\mathrm{Stha}_i(f)$$, polynomials $$u_i$$ and $$v_i$$ with $$\deg u_i\leq n-i-2$$ and $$\deg v_i\leq n-i-1$$ are computed such that $$\mathrm{Sres}_i(p,q)=u_i f + v_i f'$$. $$u_i$$ and $$v_i$$ are called the cofactors of $$\mathrm{Stha}_i(f)$$. More...

conceptSubstitute
This Functor substitutes all variables of a given multivariate PolynomialTraits_d::Polynomial_d by the values given in the iterator range, where begin refers the value for the innermost variable. More...

conceptSubstituteHomogeneous
This Functor substitutes all variables of a given multivariate PolynomialTraits_d::Polynomial_d $$p$$ by the values given in the iterator range, where begin refers the value for the innermost variable. In contrast to PolynomialTraits_d::Substitute the given polynomial $$p$$ is interpreted as a homogeneous polynomial. Hence the iterator range is required to be of length PolynomialTraits_d::d+1. More...

conceptSwap
This AdaptableFunctor swaps two variables of a multivariate polynomial. More...

conceptTotalDegree
This AdaptableUnaryFunction computes the total degree of a PolynomialTraits_d::Polynomial_d. More...

conceptTranslate
This AdaptableBinaryFunction translates a PolynomialTraits_d::Polynomial_d with respect to one variable, that is, for a given polynomial $$p$$ and constant $$c$$ it computes $$p(x+c)$$. More...

conceptTranslateHomogeneous
Given numerator $$a$$ and denominator $$b$$ this AdaptableFunctor translates a PolynomialTraits_d::Polynomial_d $$p$$ with respect to one variable by $$a/b$$, that is, it computes $$b^{degree(p)}\cdot p(x+a/b)$$. More...

conceptUnivariateContent
This AdaptableUnaryFunction computes the content of a PolynomialTraits_d::Polynomial_d with respect to the univariate (recursive) view on the polynomial, that is, it computes the gcd of all coefficients with respect to one variable. More...

conceptUnivariateContentUpToConstantFactor
This AdaptableUnaryFunction computes the content of a PolynomialTraits_d::Polynomial_d with respect to the univariate (recursive) view on the polynomial up to a constant factor (utcf), that is, it computes the $$\mathrm{gcd\_utcf}$$ of all coefficients with respect to one variable. More...

## Constants

static const int d
The dimension and the number of variables respectively.

## Types

typedef unspecified_type Polynomial_d
Type representing $$R[x_0,\dots,x_{d-1}]$$.

typedef unspecified_type Coefficient_type
Type representing $$R[x_0,\dots,x_{d-2}]$$.

typedef unspecified_type Innermost_coefficient_type
Type representing the base ring $$R$$.

typedef unspecified_type Coefficient_const_iterator
Const iterator used to iterate through all coefficients of the polynomial.

typedef unspecified_type Innermost_coefficient_const_iterator
Const iterator used to iterate through all innermost coefficients of the polynomial.

template<typename T , int d>
using Rebind = unspecified_type
This template class has to define a type Rebind<T,d>::Other which is a model of the concept PolynomialTraits_d, where d is the number of variables and T the Innermost_coefficient_type. More...

## Functors

In case a functor is not provided it is set to CGAL::Null_functor.

typedef unspecified_type Construct_polynomial
A model of PolynomialTraits_d::ConstructPolynomial.

typedef unspecified_type Get_coefficient
A model of PolynomialTraits_d::GetCoefficient.

typedef unspecified_type Get_innermost_coefficient
A model of PolynomialTraits_d::GetInnermostCoefficient.

typedef unspecified_type Construct_coefficient_const_iterator_range
A model of PolynomialTraits_d::ConstructCoefficientConstIteratorRange.

typedef unspecified_type Construct_innermost_coefficient_const_iterator_range
A model of PolynomialTraits_d::ConstructInnermostCoefficientConstIteratorRange.

typedef unspecified_type Swap
A model of PolynomialTraits_d::Swap.

typedef unspecified_type Move
A model of PolynomialTraits_d::Move.

typedef unspecified_type Degree
A model of PolynomialTraits_d::Degree.

typedef unspecified_type Total_degree
A model of PolynomialTraits_d::TotalDegree.

typedef unspecified_type Degree_vector
A model of PolynomialTraits_d::DegreeVector.

A model of PolynomialTraits_d::LeadingCoefficient.

A model of PolynomialTraits_d::InnermostLeadingCoefficient.

typedef unspecified_type Canonicalize
A model of PolynomialTraits_d::Canonicalize.

typedef unspecified_type Differentiate
A model of PolynomialTraits_d::Differentiate.

typedef unspecified_type Evaluate
A model of PolynomialTraits_d::Evaluate.

typedef unspecified_type Evaluate_homogeneous
A model of PolynomialTraits_d::EvaluateHomogeneous.

typedef unspecified_type Substitute
A model of PolynomialTraits_d::Substitute.

typedef unspecified_type Substitute_homogeneous
A model of PolynomialTraits_d::SubstituteHomogeneous.

typedef unspecified_type Is_zero_at
A model of PolynomialTraits_d::IsZeroAt.

typedef unspecified_type Is_zero_at_homogeneous
A model of PolynomialTraits_d::IsZeroAtHomogeneous.

typedef unspecified_type Sign_at
A model of PolynomialTraits_d::SignAt. More...

typedef unspecified_type Sign_at_homogeneous
A model of PolynomialTraits_d::SignAtHomogeneous. More...

typedef unspecified_type Compare
A model of PolynomialTraits_d::Compare. More...

typedef unspecified_type Univariate_content
In case PolynomialTraits_d::Coefficient_type is not a model of UniqueFactorizationDomain, this is CGAL::Null_functor, otherwise this is a model of PolynomialTraits_d::UnivariateContent.

typedef unspecified_type Multivariate_content
In case PolynomialTraits_d::Innermost_coefficient_type is not a model of UniqueFactorizationDomain, this is CGAL::Null_functor, otherwise this is a model of PolynomialTraits_d::MultivariateContent.

typedef unspecified_type Shift
A model of PolynomialTraits_d::Shift.

typedef unspecified_type Negate
A model of PolynomialTraits_d::Negate.

typedef unspecified_type Invert
A model of PolynomialTraits_d::Invert.

typedef unspecified_type Translate
A model of PolynomialTraits_d::Translate.

typedef unspecified_type Translate_homogeneous
A model of PolynomialTraits_d::TranslateHomogeneous.

typedef unspecified_type Scale
A model of PolynomialTraits_d::Scale.

typedef unspecified_type Scale_homogeneous
A model of PolynomialTraits_d::ScaleHomogeneous.

typedef unspecified_type Make_square_free
A model of PolynomialTraits_d::MakeSquareFree.

typedef unspecified_type Square_free_factorize
In case PolynomialTraits::Polynomial_d is not a model of UniqueFactorizationDomain, this is of type CGAL::Null_functor, otherwise this is a model of PolynomialTraits_d::SquareFreeFactorize.

typedef unspecified_type Pseudo_division
A model of PolynomialTraits_d::PseudoDivision.

typedef unspecified_type Pseudo_division_remainder
A model of PolynomialTraits_d::PseudoDivisionRemainder.

typedef unspecified_type Pseudo_division_quotient
A model of PolynomialTraits_d::PseudoDivisionQuotient.

typedef unspecified_type Gcd_up_to_constant_factor
A model of PolynomialTraits_d::GcdUpToConstantFactor.

typedef unspecified_type Integral_division_up_to_constant_factor
A model of PolynomialTraits_d::IntegralDivisionUpToConstantFactor.

typedef unspecified_type Content_up_to_constant_factor
A model of PolynomialTraits_d::UnivariateContentUpToConstantFactor.

typedef unspecified_type Square_free_factorize_up_to_constant_factor
A model of PolynomialTraits_d::SquareFreeFactorizeUpToConstantFactor.

typedef unspecified_type Resultant
A model of PolynomialTraits_d::Resultant.

typedef unspecified_type Polynomial_subresultants
Either CGAL::Null_functor or a model of PolynomialTraits_d::PolynomialSubresultants.

typedef unspecified_type Polynomial_subresultants_with_cofactors
Either CGAL::Null_functor or a model of PolynomialTraits_d::PolynomialSubresultants_with_cofactors.

typedef unspecified_type Principal_subresultants
Either CGAL::Null_functor or a model of PolynomialTraits_d::PrincipalSubresultants.

typedef unspecified_type Sturm_habicht_sequence
Either CGAL::Null_functor or a model of PolynomialTraits_d::SturmHabichtSequence.

typedef unspecified_type Sturm_habicht_sequence_with_cofactors
Either CGAL::Null_functor or a model of PolynomialTraits_d::SturmHabichtSequenceWithCofactors.

typedef unspecified_type Principal_sturm_habicht_sequence
Either CGAL::Null_functor or a model of PolynomialTraits_d::PrincipalSturmHabichtSequence.

## ◆ Compare

A model of PolynomialTraits_d::Compare.

In case Innermost_coefficient_type is not RealEmbeddable this is CGAL::Null_functor.

## ◆ Rebind

template<typename T , int d>

This template class has to define a type Rebind<T,d>::Other which is a model of the concept PolynomialTraits_d, where d is the number of variables and T the Innermost_coefficient_type.

Note
It can be implemented using a nested template class.

## ◆ Sign_at

A model of PolynomialTraits_d::SignAt.

In case Innermost_coefficient_type is not RealEmbeddable this is CGAL::Null_functor.

## ◆ Sign_at_homogeneous

A model of PolynomialTraits_d::SignAtHomogeneous.

In case Innermost_coefficient_type is not RealEmbeddable this is CGAL::Null_functor.