Kinetic::FunctionKernel

Definition

The concept Kinetic::FunctionKernel encapsulates all the methods for representing and handing functions. The set is kept deliberately small to easy use of new Kinetic::FunctionKernels, but together these operations are sufficient to allow the correct processing of events, handling of degeneracies, usage of static data structures, run-time error checking as well as run-time verification of the correctness of kinetic data structures. The computation of a polynomial with the variable negated is used for reversing time in kinetic data structures and can be omitted if that capability is not needed.

Types

Each of the following types has a corresponding type_object method (not explicitly documented) which takes a Function as an argument.

The following type is used to construct functions from a list of coefficients. To get an instance use the construct_function_object() method.

The following functor likewise have a type_object method, but these take arguments other than a Function. The arguments are given below.

The following methods do not require any arguments to get the functor and take one Function as a functor argument.

Has Models

See Also

Kinetic::RootEnumerator.

Example

We provide several models of the concept, which are not documented separately. The models of Kinetic::SimulationTraits all choose appropriate models. However, if more control is desired, we here provide examples of how to create the various supported Kinetic::FunctionKernel.

A Sturm sequence based kernel which supports exact comparisons of roots of polynomials (certificate failure times):

typedef CGAL::POLYNOMIAL::Polynomial<CGAL::Gmpq> Function;
typedef CGAL::POLYNOMIAL::Sturm_root_stack_traits<Function> Root_stack_traits;
typedef CGAL::POLYNOMIAL::Sturm_root_stack<Root_stack_traits> Root_stack;
typedef CGAL::POLYNOMIAL::Kernel<Function, Root_stack> Function_kernel;

A wrapper for CORE::Expr which implements the necessary operations:

typedef CGAL::POLYNOMIAL::CORE_kernel Function_kernel;

A function kernel which computes approximations to the roots of the polynomials:

typedef CGAL::POLYNOMIAL::Polynomial<double> Function;
typedef CGAL::POLYNOMIAL::Root_stack_default_traits<Function> Root_stack_traits;
typedef CGAL::POLYNOMIAL::Numeric_root_stack<Root_stack_traits> Root_stack;
typedef CGAL::POLYNOMIAL::Kernel<Function, Root_stack> Function_kernel;

When using the function kernel in kinetic data structures, especially one that is in exact, it is useful to wrap the root stack. The wrapper checks the sign of the certificate function being solved and uses that to handle degeneracies. This is done by, for the inexact solvers

typedef Kinetic::Derivitive_filter_function_kernel<Function_kernel> KDS_function_kernel;

typedef Kinetic::Handle_degeneracy_function_kernel<Function_kernel> KDS_function_kernel;

For exact computations, the primary representation for roots is the now standard choice of a polynomial with an associated isolating interval (and interval containing exactly one distinct root of a polynomial) along with whether the root has odd or even multiplicity and, if needed, the Sturm sequence of the polynomial. Two intervals can be compared by first seeing if the isolating intervals are disjoint. If they are, then we know the ordering of the respective roots. If not we can subdivide each of the intervals (using the endpoints of the other interval) and repeat. In order to avoid subdividing endlessly when comparing equal roots, once we subdivide a constant number of times, we use the Sturm sequence of $$p and $$p'q (where $$p and $$q are the two polynomials and $$p' is the derivative of $$p) to evaluate the sign of the second at the root of the first one directly (note that this Sturm sequence is applied to a common isolating interval of the roots of interest of both polynomials).