|
CGAL 5.5.1 - Polynomial
|
Note that this is just a very brief introduction to polynomials. For a quick reference we refer to the Wikipedia or for a more elaborate introduction to any class book on elementary algebra.
A polynomial is either zero, or can be written as the sum of one or more non-zero terms. The number of terms is finite. A term consist of a constant coefficient and a monomial, that is, the product of zero or more variables. Each variable may have an exponent that is a non-negative integer. The exponent on a variable in a term is equal to the degree of that variable in that term. A term with no variables is called a constant term. The degree of a constant term is 0.
For example, \( -7x^3y\) is a term. The coefficient is \( -7\), the monomial is \( x^3y\), comprised of the variables \( x\) and \( y\), the degree of \( x\) is three, and the degree of \( y\) is one. The total degree of the entire term is the sum of the degrees in each variable. In the example above, the degree is \( 3 + 1 = 4\).
A one-variable (univariate) polynomial \( f\) of degree \( n\) has the following form:
\[ f = a_nx^n + a_{n-1}x^{n-1} + ... + a_2x^2 + a_1x + a_0 \]
The coefficient \( a_0\) is called the constant coefficient, \( a_n\) is called the leading coefficient. If \( f\) is not the zero polynomial the leading coefficient is not zero. The polynomial is called monic if \( a_n = 1\). In case the coefficient domain of \( f\) possess a greatest common divisor (gcd) the content of \( f\) is the gcd of all coefficients of \( f\). For instance, the content of \( 12 x^3 + 6\) is \( 6\).
A multivariate polynomial is a polynomial in more than one variable. According to the number of variables it is possible to further classify multivariate polynomials as bivariate, trivariate etc. In contrast to univariate polynomials the terms of a multivariate polynomial are not completely ordered by their total degree. However, given a certain order on the variables it is possible to define a lexicographic order on the terms. Given this order the leading coefficient of a multivariate polynomial is defined as the coefficient of the highest term. For instance the leading coefficient of the multivariate polynomial \( p = 5 x^3y + 7xy^2\) is \( 7\), given that \( y\) has an higher order than \( x\).
However, it is also possible to interpret a multivariate polynomial as a univariate polynomial in that variable. For instance the trivariate polynomial
\[ q = x^5 + 7x^2y^1z^2 + 13x^1y^2z^2 \in \Z[x,y,z] \]
may be interpreted as a univariate polynomial in \( z\), that is, \( q\) is interpreted as an element of \( R[z]\), with \( R=\Z[x,y]\).
\[ q = (13x^1y^2 + 7x^2y^1)z^2 + x^5z^0 \in R[z] \]
In this case the leading coefficient of \( q\) with respect to \( z\) is \( 13x^1y^2 + 7x^2y^1\) and \( x^5\) becomes the 'constant' term.
A homogeneous polynomial is a polynomial whose terms do all have the same total degree. For example, \( h = x^5 + 7x^2y^1z^2 + 13x^1y^2z^2\) is a homogeneous polynomial of degree \( 5\), in three variables.
The package introduces a concept Polynomial_d, a concept for multivariate polynomials in \( d\) variables. Though the concept is written for an arbitrary number of variables, the number of variables is considered as fixed for a particular model of Polynomial_d. The concept also allows univariate polynomials.
First of all a model of Polynomial_d is considered as an algebraic structure, that is, the ring operations \( \{+, -, \cdot\}\) are provided due to the fact that Polynomial_d refines at least the concept IntegralDomainWithoutDivision. However, a model of Polynomial_d has to be accompanied by a traits class Polynomial_traits_d<Polynomial_d> being a model of PolynomialTraits_d. This traits class provides all further functionalities on polynomials.
Given a \( d\)-variate polynomial over some base ring \( R\) there are at least two different possible views on such a polynomial.
According to these two different views the traits class is required to provide two different coefficient types:
Polynomial_traits_d::Coefficient_type representing \( R[x_0,\dots,x_{d-2}]\). Polynomial_traits_d::Innermost_coefficient_type representing the base ring \( R\). Another important type which is introduced by this package is Exponent_vector. It is derived from std::vector<int> and used to identify multivariate monomials. For instance the exponent vector containing the sequence \( [3,2,4]\) corresponds to the trivariate monomial \( x_0^3x_1^2x_2^4\). Note that a vector with negative exponents is considered as invalid. However, we allow negative exponents as they may appear as intermediate results, in particular we did not derive from std::vector<unsigned int>.
First of all the concept Polynomial_d requires that the model is constructible from int. This is due to the fact that Polynomial_d refines IntegralDomainWithoutDivision which in turn refines FromIntConstructible. Of course this allows only the construction of constant polynomials.
In general a polynomial is constructed using the functor Polynomial_traits_d::Construct_polynomial a model of PolynomialTraits_d::ConstructPolynomial. Basically there are two options:
Polynomial_traits_d::Coefficient_type, where the begin iterator refers to the constant term (constant with respect to the outermost variable). std::pair<Exponent_vector, Polynomial_traits_d::Innermost_coefficient_type>, where each pair defines the coefficient for the monomial defined by the exponent vector. However, in some cases it might be more convenient to just construct the polynomials representing the different variables and to obtain the final polynomial using algebraic expressions. The most elegant way to construct a certain variable is Polynomial_traits_d::Shift being a model of PolynomialTraits_d::Shift.
The following example illustrates different ways to construct a bivariate polynomial:
File Polynomial/construction.cpp
In order to obtain a certain coefficient the traits class provides several functors. Note that the functors do not allow a write access to the coefficients.
PolynomialTraits_d::GetCoefficient: a model of this concept provides access to a coefficient in the univariate view, that is, it returns elements of \( R[x_0,\dots,x_{d-2}]\). PolynomialTraits_d::GetInnermostCoefficient: a model of this concept provides access to a coefficient in the multivariate view, that is, it returns elements of \( R\). PolynomialTraits_d::LeadingCoefficient: a model of this concept provides access to the leading coefficient in the univariate view. PolynomialTraits_d::InnermostLeadingCoefficient: a model of this concept provides access to the leading coefficient in the multivariate view, that is, it returns the (innermost) coefficient of the leading multivariate monomial. See also PolynomialTraits_d::DegreeVector. The following example illustrates the application of the functors discussed above:
File Polynomial/coefficient_access.cpp
There are three functors in PolynomialTraits_d related to the degree of a polynomial.
PolynomialTraits_d::Degree: a model of this concept returns the degree of the polynomial in the univariate view. By default this is the degree with respect to the outermost variable, but it is also possible to select another variable. PolynomialTraits_d::TotalDegree: a model of this concept returns the total degree of a polynomial. The polynomial is considered as a multivariate polynomial. The total degree is the maximum over the sums of the exponents of each multivariate monomial. PolynomialTraits_d::DegreeVector: a model of this concept returns the exponent vector of the leading monomial, where the monomial order is lexicographic and starts with the outermost variable. See also PolynomialTraits_d::InnermostLeadingCoefficient. The following example illustrates the application of the functors discussed above:
File Polynomial/degree.cpp
Given for instance a bivariate polynomial it is conceivable that one wants to interchange the role of \( x\) and \( y\). That is one wants to interpret the \( x\) as \( y\) and vice versa. For such a case the polynomial traits provides PolynomialTraits_d::Swap:
Given a polynomial \( p\) and to two indices \( i\) and \( j\), the functor returns the polynomial in which \( x_i\) is substituted by \( x_j\) and vice versa, that is, the variables swap their positions. The order of the other variables remains untouched.
Another scenario is, that a particular variable should be moved to another position, for instance, it should become the outermost variable while the relative order of the other variables remains unchanged. For such a case the polynomial traits provides PolynomialTraits_d::Move.
Of course there is also a general method to interchange the order of variables, namely PolynomialTraits_d::Permute.
The following example illustrates the application of the functors discussed above:
File Polynomial/swap_move.cpp
Since the concept PolynomialTraits_d refines the concept AlgebraicStructureTraits the polynomial traits provides functors for integral division, division with remainder, greatest common divisor, etc. But note that the algebraic structure of a polynomial depends on the algebraic structure of the innermost coefficient, for instance, a gcd is available if and only if the innermost coefficient is a Field or a UniqueFactorizationDomain. Hence, we can not provide a \( gcd\) if the innermost coefficient is just an IntegralDomain since it is simply not well definedAn example for such a number type is the template Sqrt_extension<NT,ROOT> representing an algebraic extension of degree two. This is just an IntegralDomain if NT is not a Field. . However, if we would consider the polynomial over the quotient field of the integral domain the \( gcd\) would be well defined. The only problem is that the result can not be represented over the ring since it contains denominators. Therefore, the PolynomialTraits_d requires functors such as PolynomialTraits_d::GcdUpToConstantFactor. This functor computes the gcd of two polynomials up to a constant factor (utcf). That is, it returns the correct gcd for polynomials over the quotient field, but multiplied by some constant such that the result is representable with coefficients in the ring.
However, note that these 'utcf' functions are usually a bit faster than their strict counterparts. This is due to the fact that the 'utcf' functions are allowed to skip the computation of the correct constant factor. Note that in many cases the constant factor is in fact not needed. In particular if the polynomials are supposed to represent some zero set, that is, an algebraic curve or surface.
The concepts for the related functors are:
AlgebraicStructureTraits::IntegralDivision
Another analog functionality is the pseudo division. The related functors replace the usual division with remainder in case the Polynomial is not a EuclideanRing.
The concepts for the related functors are:
The following example illustrates the application of some functors discussed above:
File Polynomial/gcd_up_to_constant_factor.cpp
Of course, it should also be possible to evaluate a polynomial or substitute its variables. We also require a special functor to determine whether a polynomial is zero at a given point. In case the inner most coefficient is RealEmbeddable the traits also must provide a function to compute the sign at a given point.
The concepts for the related functors are:
PolynomialTraits_d::SubstitutePolynomialTraits_d::EvaluatePolynomialTraits_d::IsZeroAtPolynomialTraits_d::SignAt The traits is also required to provide variants of these functors that interpret the polynomial as a homogeneous polynomial by adding a virtual homogeneous variable such that each term has the same degree, namely the degree of the polynomial. Of course there is a difference between the univariate and multivariate view. For instance the polynomial
\[ 5x^3 + 7x - 3 \]
has degree 3, hence it is interpreted as the homogeneous polynomial
\[ 5x^3 + 7xw^2 -3w^3 \]
by adding the homogeneous variable \( w\). In case of the multivariate view each term is filled up by the homogeneous variable such that the degree of each term is equal to the total degree of the polynomial. Note that these functors may significantly improve efficiency. For instance, it is possible to determine the sign of a polynomial over integer coefficients at a rational point without changing the coefficient domain of the polynomial. For more details have a look at the following concepts:
PolynomialTraits_d::SubstituteHomogeneous PolynomialTraits_d::EvaluateHomogeneousPolynomialTraits_d::IsZeroAtHomogeneousPolynomialTraits_d::SignAtHomogeneous Note that substitute allows the substitution of the variables by any type that is ExplicitInteroperable with the innermost coefficient type. This is a very powerful tool since it allows the substitution of the variables by polynomials. However, for some standard manipulations such as translation or scaling we require special functors since they are expected to be faster than their equivalent implementation using substitution:
PolynomialTraits_d::ShiftPolynomialTraits_d::NegatePolynomialTraits_d::InvertPolynomialTraits_d::TranslatePolynomialTraits_d::TranslateHomogeneousPolynomialTraits_d::ScalePolynomialTraits_d::ScaleHomogeneous The following example illustrates the application of some functors discussed above:
File Polynomial/substitute.cpp
The PolynomialTraits_d concept also provides more sophisticated functors for computations with polynomials - computing the resultant of two polynomials, their polynomial subresultant sequence, with or without cofactors, and their principal subresultant coefficients.
PolynomialTraits_d::ResultantPolynomialTraits_d::PolynomialSubresultantsPolynomialTraits_d::PolynomialSubresultantsWithCofactorsPolynomialTraits_d::PrincipalSubresultants Moreover, functors to compute the Sturm-Habicht sequence, with or without cofactors, and for the principal Sturm-Habicht coefficients exist.
PolynomialTraits_d::SturmHabichtSequencePolynomialTraits_d::SturmHabichtSequenceWithCofactorsPolynomialTraits_d::PrincipalSturmHabichtSequence For a formal definition of all used terms, we refer to the corresponding reference pages.
The principal Sturm-Habicht sequence allows to count the number of real roots of a polynomial using the function
As input, this function requires an iterator range that represents the principal Sturm-Habicht coefficients. This might look complicated at a first sight, as one has to store the principal Sturm-Habicht sequence temporarily. However, we remark an important property of the (principal) Sturm-Habicht sequence. Having a polynomial \( f_t(x)\) that depends on a parameter \( t\), and its (principal) Sturm-Habicht coefficients \( \mathrm{stha}_0(f_t),\ldots,\mathrm{stha}_n(f_t)\), evaluating \( \mathrm{stha}_0(f_t)\) for \( t=t_0\) yields a valid (principal) Sturm-Habicht sequence for \( f_{t_0}\). The same holds for (principal) subresultants. Thus, it is enough in such situations to compute the sequence once for the parameter \( t\), and call number_of_real_roots() for each specialized parameter value.
We finally remark that computing subresultants and Sturm-Habicht sequences introduces an enormous coefficient blow-up. An application of the functors therefore does not make sense for built-in integers except for toy examples. To avoid overflows, one should use arbitrary size integer types in real applications.
The following example illustrates how two compute resultants of two polynomials, and how to count the number of distinct real roots of a polynomial using its principal Sturm-Habicht coefficients.
File Polynomial/subresultants.cpp
This package is the result of the integration process of the NumeriX library of Exacus [1] into CGAL.
The class Polynomial<Coeff> had been started by Michael Seel within CGAL as part of the Nef_2 package. As part of the Exacus project it got significantly improved by Arno Eigenwillig and Michael Hemmer.
However, due to the recursive definition the class was rather restricted to the univariate view. Moreover, it is clear that depending on the context other classes that are symmetric in all variables or dedicated for sparse polynomials may be more efficient. As a consequence this package introduced the Polynomial_traits_d<Polynomial_d> giving also the symmetric view on polynomials and the opportunity to introduce and use other classes representing polynomials within CGAL.
1.8.13