Partitioning

The ETF algorithm requires a pre-processing step whereby a majorizing function for the probability density function is sought in the form of equal-area contiguous vertical rectangles sitting on the x axis. The support of these rectangles over the x axis defines the ETF partition.

At the moment, the only partition solvers implemented are based on a multi-variate Newton method:

template<class Func, class DFunc, class InputIt1, class InputIt2>
partition_data<typename std::iterator_traits<InputIt1>::value_type>
newton_partition(
    Func f,
    DFunc df,
    InputIt1 x_initial_first,
    InputIt1 x_initial_last,
    InputIt2 x_extremum_first,
    InputIt2 x_extremum_last,
    typename std::iterator_traits<InputIt1>::value_type eps,
    typename std::iterator_traits<InputIt1>::value_type relax = 1,
    unsigned int max_iter = 100);
template<class Func, class DFunc, class InputIt1>
partition_data<typename std::iterator_traits<InputIt1>::value_type>
newton_partition_monotonic(
    Func f,
    DFunc df,
    InputIt1 x_initial_first,
    InputIt1 x_initial_last,
    typename std::iterator_traits<InputIt1>::value_type eps,
    typename std::iterator_traits<InputIt1>::value_type relax = 1,
    unsigned int max_iter = 100);

The second solver is a specialization for the case of monotonic probability density functions.

These solvers compute an ETF partition of the interval bounded by the first and last points of the vector of abcissae passed in argument. The returned object include the partition as well the infimum and supremum of the function over each sub-interval.

For faster convergence it is recommended to provide a reasonable initial estimate of the partition abcissae passed in arguments.

The derivative df of f must be provided. For non-monotonic probability density functions, an ordered sequence of the x abcissae of inner function extrema (boundary points excluded) must as well be provided.

The tolerance is the maximum relative dispersion of upper rectangle areas, computed as the difference between the largest and smallest area relative to the average area.

An object with empty tables (size 0) is returned if the algorithm fails to converge.

In order to improve convergence robustness (respectively convergence rate), successive under-relaxation (respectively over-relaxation) may be optionally requested by setting the relaxation factor to less (respectively more) than 1.

The maximum number of iterations may be optionally specified but the default value is rather conservative and should prove adequate for most cases unless a very small relaxation factor is used.

The complexity of these solvers is Ο(N) where N is the number of sub-intervals. For sufficiently well-behaved functions the convergence rate is quadratic with respect to tolerance eps.

Arguments

Argument Description
f Function proportional to the probability density function
df Derivative of f
x_initial_first, x_initial_last Input iterator range of an ordered sequence of abcissae defining a partition of a bounded interval for which the rectangles making up an upper Riemann sum of func have, preferably, approximately equal areas
x_extremum_first, x_extremum_last Input iterator range of an ordered sequence of the abcissae x at which f has a local extremum, excluding boundary points
eps Tolerance, defined as the maximum dispersion of upper rectangle areas relatively to the average rectangle area
relax Relaxation factor for the iterative Newton solver
max_iter Maximum number of iteration of the Newton method before giving up

Return value

The return value is a struct with 3 public member variables:

template<typename RealType>
struct partition_data
{
    std::vector<RealType> x;
    std::vector<RealType> finf;
    std::vector<RealType> fsup;
};

Upon successful convergence of the solver, the members of the return value satisfy the following post-conditions:

  • size(x)==std::distance(x_initial_first, x_initial_last)

  • size(finf)==size(x)-1

  • size(fsup)==size(x)-1

If the solver fails to converge after max_iter iterations, however, the post-conditions become:

  • size(x)==0

  • size(finf)==0

  • size(fsup)==0

Member variable Description
x Sequence of abcissae defining the ETF partition
finf Sequence of infima for each of the partition sub-interval
fsup Sequence of suprema for each of the partition sub-interval