A resampler is a function object called as r(weights, ancestors, rng).
It fills every element of ancestors with an index into weights, drawn so that index i is chosen in proportion to weights[i]. weights are nonnegative linear weights with a positive sum; they need not be normalized. Zero-weight indices are never chosen. ancestors may be any length.
The four resamplers are the ones Hol, Schön, and Gustafsson (2006) compare; Arulampalam et al. (2002) describe their place in a particle filter. All four invert the cumulative sum of the weights at a set of positions in [0, 1), and differ only in how the positions are drawn (internal::invertCumulative()).
A resampler that needs storage sized by the counts, as resamplers::Multinomial and resamplers::Residual do, also takes it: r(weights, ancestors, rng, scratch) with scratch a std::span<Scalar> of at least weights.size() + ancestors.size() elements it may use freely (ResamplerWithScratch). ParticleSet::resample() keeps that scratch and passes it, so such a resampler allocates nothing there, while its three-argument form allocates what it needs (see Allocation). resamplers::Stratified and resamplers::Systematic need none.
Each also runs under an execution policy as r(policy, weights, ancestors, rng) (see Execution policies). The draws stay sequential, in the order the sequential form takes them; the cumulative sum is then a scan under the policy and each ancestor a binary search into it. The sum is the one collective operation that Murray, Lee, and Jacob (2016) find these resamplers need in parallel. The ancestors are Sequential's but for rounding at the boundaries between particles, except that resamplers::Multinomial leaves them in the order of its draws rather than sorted, which is the same draw of ancestors.
- See also
- ParticleSet::resample()
1.18.0