Pre-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.
Pre-partitioning consists in finding a first approximation of the ETF partition of the x axis to be used by the final partition solver.
At the moment, a trivial (but fast) pre-partitioning algorithm based on the trapezoidal rule is available:
template<typename RealType, class Func>
std::vector<RealType>
trapezoidal_rule_prepartition(Func f,
RealType x0,
RealType x1,
std::size_t nb_intervals,
std::size_t nb_points);
template<typename RealType, class Func>
std::vector<RealType>
trapezoidal_rule_prepartition(Func f,
RealType x0,
RealType x1,
std::size_t nb_intervals);
where the second overload is equivalent to setting nb_points to
nb_partitions.
These functions apply the trapezoidal rule to the supplied function f over a
regular grid with nb_points grid points (including boundary nodes) to divide
interval [x0, x1] into the specified number of sub-intervals such that the
areas under the trapeze quadrature are the same in each sub-interval. The
returned vector is the set of abscissae.
Arguments
| Argument | Description |
f | Function proportional to the probability density function |
x0, x1 | Boundaries of the interval |
nb_intervals | Number of sub-intervals in the generated partition |
nb_points | Number of points (including boundary nodes) to be used for the trapezoidal rule |
Return value
The set of abcissae defining the partition.