A practical introduction to butterfly and adaptive resampling in Sequential Monte Carlo

Parallel and distributed computing technologies offer great potential for speed-up of Monte Carlo algorithms. However, in the development of most existing algorithms it has been implicitly assumed that implementation would be on a serial machine, so algorithm structure is often not well-suited to parallel architectures. In recent work the authors have studied the theoretical properties of sequential Monte Carlo algorithms involving a \buttery" resampling method, whose conditional independence structure is intended to better match parallel and distributed architectures, with resampling broken down into stages, allowing sampling tasks for subsets of the particles to be handled concurrently. This paper provides a more practical overview of these methods, including consideration of adaptive resampling schemes, numerical results and an accessible account of theoretical properties.