Parallelising particle filters with butterfly interactions
29th September 2017, 2:00 pm – 3:00 pm
Main Maths Building, SM3
In modern computing systems an increase in the computational power is primarily obtained by increasing the number of parallel processing elements (PE) rather than by increasing the speed of an individual PE. While in many cases such parallel computing systems have enabled the completion of increasingly complex computational tasks, they can only do so if the task in question admits parallel computations. This talk focuses on an important class of algorithms lacking such inherent parallelism, namely the sequential Monte Carlo (SMC) methods, or particle filters. We consider some new parallel particle filter algorithms whose interaction diagram coincides with the butterfly diagram best known from the context of fast Fourier transform. We present some new convergence results and consider the potential of these algorithms based on numerical experiments.
Joint work with Nick Whiteley (University of Bristol) and Ali Taylan Cemgil (Bogazici University)