\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.14 - Polynomial

Concepts

conceptPolynomial_d
 A model of Polynomial_d is representing a multivariate polynomial in \( d \geq 1\) variables over some basic ring \( R\). This type is denoted as the innermost coefficient. A model of Polynomial_d must be accompanied by a traits class CGAL::Polynomial_traits_d<Polynomial_d>, which is a model of PolynomialTraits_d. Please have a look at the concept PolynomialTraits_d, since nearly all functionality related to polynomials is provided by the traits. More...
 
conceptPolynomialTraits_d::Canonicalize
 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...

 
conceptPolynomialTraits_d::Compare
 This AdaptableBinaryFunction compares two polynomials, with respect to the lexicographic order with preference to the outermost variable. More...
 
conceptPolynomialTraits_d::ConstructCoefficientConstIteratorRange
 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...
 
conceptPolynomialTraits_d::ConstructInnermostCoefficientConstIteratorRange
 This AdaptableUnaryFunction returns a const iterator range over all innermost coefficients of the given polynomial. More...
 
conceptPolynomialTraits_d::ConstructPolynomial
 This AdaptableFunctor provides several operators to construct objects of type PolynomialTraits_d::Polynomial_d. More...
 
conceptPolynomialTraits_d::Degree
 This AdaptableUnaryFunction computes the degree of a PolynomialTraits_d::Polynomial_d with respect to a certain variable. More...
 
conceptPolynomialTraits_d::DegreeVector
 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...
 
conceptPolynomialTraits_d::Differentiate
 This AdaptableUnaryFunction computes the derivative of a PolynomialTraits_d::Polynomial_d with respect to one variable. More...
 
conceptPolynomialTraits_d::Evaluate
 This AdaptableBinaryFunction evaluates PolynomialTraits_d::Polynomial_d with respect to one variable. More...
 
conceptPolynomialTraits_d::EvaluateHomogeneous
 This AdaptableFunctor provides evaluation of a PolynomialTraits_d::Polynomial_d interpreted as a homogeneous polynomial in one variable. More...
 
conceptPolynomialTraits_d::GcdUpToConstantFactor
 This AdaptableBinaryFunction computes the \( gcd\) up to a constant factor (utcf) of two polynomials of type PolynomialTraits_d::Polynomial_d. More...
 
conceptPolynomialTraits_d::GetCoefficient
 This AdaptableBinaryFunction provides access to coefficients of a PolynomialTraits_d::Polynomial_d. More...
 
conceptPolynomialTraits_d::GetInnermostCoefficient
 For the given PolynomialTraits_d::Polynomial_d this AdaptableBinaryFunction returns the coefficient of the (multivariate) monomial specified by the given CGAL::Exponent_vector. More...
 
conceptPolynomialTraits_d::InnermostLeadingCoefficient
 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...
 
conceptPolynomialTraits_d::IntegralDivisionUpToConstantFactor
 This AdaptableBinaryFunction computes the integral division of two polynomials of type PolynomialTraits_d::Polynomial_d up to a constant factor (utcf) . More...
 
conceptPolynomialTraits_d::Invert
 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...
 
conceptPolynomialTraits_d::IsSquareFree
 This AdaptableUnaryFunction computes whether the given a polynomial of type PolynomialTraits_d::Polynomial_d is square free. More...
 
conceptPolynomialTraits_d::IsZeroAt
 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...
 
conceptPolynomialTraits_d::IsZeroAtHomogeneous
 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...
 
conceptPolynomialTraits_d::LeadingCoefficient
 This AdaptableUnaryFunction computes the leading coefficient of a PolynomialTraits_d::Polynomial_d. More...
 
conceptPolynomialTraits_d::MakeSquareFree
 This AdaptableUnaryFunction computes the square-free part of a polynomial of type PolynomialTraits_d::Polynomial_d up to a constant factor. More...
 
conceptPolynomialTraits_d::MonomialRepresentation
 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...
 
conceptPolynomialTraits_d::Move
 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...
 
conceptPolynomialTraits_d::MultivariateContent
 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...
 
conceptPolynomialTraits_d::Negate
 This AdaptableUnaryFunction computes \( p(-x)\) for a given polynomial \( p\). More...
 
conceptPolynomialTraits_d::Permute
 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...
 
conceptPolynomialTraits_d::PolynomialSubresultants
 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...
 
conceptPolynomialTraits_d::PolynomialSubresultantsWithCofactors
 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...
 
conceptPolynomialTraits_d::PrincipalSturmHabichtSequence
 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...
 
conceptPolynomialTraits_d::PrincipalSubresultants
 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...
 
conceptPolynomialTraits_d::PseudoDivision
 This AdaptableFunctor computes the pseudo division of two polynomials \( f\) and \( g\). More...
 
conceptPolynomialTraits_d::PseudoDivisionQuotient
 This AdaptableBinaryFunction computes the quotient of the pseudo division of two polynomials \( f\) and \( g\). More...
 
conceptPolynomialTraits_d::PseudoDivisionRemainder
 This AdaptableBinaryFunction computes the remainder of the pseudo division of two polynomials \( f\) and \( g\). More...
 
conceptPolynomialTraits_d::Resultant
 This AdaptableBinaryFunction computes the resultant of two polynomials \( f\) and \( g\) of type PolynomialTraits_d::Polynomial_d with respect to a certain variable. More...
 
conceptPolynomialTraits_d::Scale
 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...
 
conceptPolynomialTraits_d::ScaleHomogeneous
 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...
 
conceptPolynomialTraits_d::Shift
 This AdaptableBinaryFunction multiplies a PolynomialTraits_d::Polynomial_d by the given power of the specified variable. More...
 
conceptPolynomialTraits_d::SignAt
 This AdaptableFunctor returns the sign of a PolynomialTraits_d::Polynomial_d \( p\) at given Cartesian point represented as an iterator range. More...
 
conceptPolynomialTraits_d::SignAtHomogeneous
 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...
 
conceptPolynomialTraits_d::SquareFreeFactorize
 This Functor computes a square-free factorization of a PolynomialTraits_d::Polynomial_d. More...
 
conceptPolynomialTraits_d::SquareFreeFactorizeUpToConstantFactor
 This AdaptableFunctor computes a square-free factorization up to a constant factor (utcf) of a PolynomialTraits_d::Polynomial_d. More...
 
conceptPolynomialTraits_d::SturmHabichtSequence
 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...
 
conceptPolynomialTraits_d::SturmHabichtSequenceWithCofactors
 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...
 
conceptPolynomialTraits_d::Substitute
 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...
 
conceptPolynomialTraits_d::SubstituteHomogeneous
 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...
 
conceptPolynomialTraits_d::Swap
 This AdaptableFunctor swaps two variables of a multivariate polynomial. More...
 
conceptPolynomialTraits_d::TotalDegree
 This AdaptableUnaryFunction computes the total degree of a PolynomialTraits_d::Polynomial_d. More...
 
conceptPolynomialTraits_d::Translate
 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...
 
conceptPolynomialTraits_d::TranslateHomogeneous
 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...
 
conceptPolynomialTraits_d::UnivariateContent
 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...
 
conceptPolynomialTraits_d::UnivariateContentUpToConstantFactor
 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...
 
conceptPolynomialTraits_d
 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. More...