Vectorized and parallel particle filter SMC parameter estimation for stiff ODEs

Previous Article
Stabilization of a hyperbolic/elliptic system modelling the viscoelastic-gravitational deformation in a multilayered Earth
PROC Home
This Issue
Next Article
Canard-type solutions in epidemiological models

2015, 2015(special): 75-84. doi: 10.3934/proc.2015.0075

Vectorized and parallel particle filter SMC parameter estimation for stiff ODEs

Andrea Arnold ^1, , Daniela Calvetti ^2, and Erkki Somersalo ^3,

1.	Department of Mathematics, North Carolina State University, Campus Box 8205, 2311 Stinson Drive, 2108 SAS Hall, Raleigh, NC 27695-8205, United States
2.	Case Western Reserve University, Department of Mathematics and Center for Modelling Integrated Metabolic Systems, 10900 Euclid Avenue, Cleveland, OH 44106
3.	Case Western Reserve University, Department of Mathematics, Applied Mathematics, and Statistics, Cleveland, OH 44106

Received August 2014 Revised September 2015 Published November 2015

Abstract
Related Papers

Particle filter (PF) sequential Monte Carlo (SMC) methods are very attractive for estimating parameters of time-dependent systems where the data is either not all available at once, or the range of time constants is wide enough to create problems in the numerical time propagation of the states. The need to evolve (and hence integrate) a large number of particles makes PF-based methods computationally challenging, and parallelization is often advocated to speed up computing time. While careful parallelization may indeed improve performance, vectorization of the algorithm on a single processor may result in even larger speedups for certain problems. In this paper we demonstrate how the PF-SMC class of algorithms proposed in [2] can be implemented in both parallel and vectorized computing environments, illustrating the performance with computed examples in MATLAB. In particular, two stiff test problems with different features show that both the size and structure of the problem affect which version of the algorithm is more efficient.

Keywords: vectorization, Markov chain Monte Carlo, linear multistep methods., Parallel computing, particle lters.

Mathematics Subject Classification: Primary: 65Y05, 65Y10; Secondary: 62M20, 65L06, 62M0.

Citation: Andrea Arnold, Daniela Calvetti, Erkki Somersalo. Vectorized and parallel particle filter SMC parameter estimation for stiff ODEs. Conference Publications, 2015, 2015 (special) : 75-84. doi: 10.3934/proc.2015.0075

References:

[1]	A. Arnold, Sequential Monte Carlo Parameter Estimation for Differential Equations,, Ph.D thesis, (2014).
[2]	A. Arnold, D. Calvetti and E. Somersalo, Linear multistep methods, particle filtering and sequential Monte Carlo,, Inverse Problems, 29 (2013).
[3]	O. Brun, V. Teuliere and J.-M. Garcia, Parallel particle filtering,, Journal of Parallel and Distributed Computing, 62 (2002), 1186.
[4]	B. Calderhead, M. Girolami and N. D. Lawrence, Accelerating Bayesian inference over nonlinear differential equations with Gaussian processes,, Adv. Neural Inf. Process. Syst., 21 (2009), 217.
[5]	D. Calvetti and E. Somersalo, Large scale statistical parameter estimation in complex systems with an application to metabolic models,, Multiscale Model. Simul., 5 (2006), 1333.
[6]	N. Chopin, P. E. Jacob and O. Papaspiliopoulos, SMC$^2$: an efficient algorithm for sequential analysis of state space models,, J. R. Stat. Soc. Ser. B Stat. Methodol., 75 (2013), 397.
[7]	A. Golightly and D. J. Wilkinson, Bayesian parameter inference for stochastic biochemical network models using particle MCMC,, J. R. Soc. Interface Focus, 1 (2011), 807.
[8]	A. Iserles, A First Course in the Numerical Analysis of Differential Equations,, $2^{nd}$ edition, (2009).
[9]	A. Lee, C. Yau, M. B. Giles, A. Doucet and C. C. Holmes, On the utility of graphics cards to perform massively parallel simulation of advanced Monte Carlo methods,, J. Comput. Graph. Statist., 19 (2010), 769.
[10]	R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations,, SIAM, (2007).
[11]	C. Lieberman and K. Willcox, Goal-oriented inference: approach, linear theory, and application to advection diffusion,, SIAM Review, 55 (2013), 493.
[12]	J. Liu and M. West, Combined parameter and state estimation in simulation-based filtering,, in Sequential Monte Carlo Methods in Practice* (eds. A. Doucet*, (2001), 197.
[13]	S. Maskell, B. Alun-Jones and M. Macleod, A single instruction multiple data particle filter,, Nonlinear Statistical Signal Processing Workshop 2006 IEEE, (2006), 51.
[14]	L. M. Murray, Bayesian state-space modelling on high-performance hardware using LibBi, preprint,, , ().
[15]	M. Pitt and N. Shephard, Filtering via simulation: auxiliary particle filters,, J. Amer. Statist. Assoc., 94 (1999), 590.
[16]	R. Ren and G. Orkoulas, Parallel Markov chain Monte Carlo simulations,, The Journal of Chemical Physics, 126 (2007).
[17]	L. R. Scott, T. Clark and B. Bagheri, Scientific Parallel Computing,, Princeton, (2005).
[18]	M. West, Approximating posterior distributions by mixtures,, J. R. Stat. Soc. Ser. B Stat. Methodol., 55 (1993), 409.
[19]	M. West, Mixture models, Monte Carlo, Bayesian updating and dynamic models,, in Computing Science and Statistics: Proceedings of the 24th Symposium on the Interface* (ed. J. H. Newton)*, (1993), 325.
[20]	D. J. Wilkinson, Parallel Bayesian computation,, in Handbook of Parallel Computing and Statistics* (ed. E. J. Kontoghiorghes)*, (2005), 477.
[21]	Y. Zhou, vSMC: Parallel sequential Monte Carlo in C++, preprint,, , ().

show all references

References:

[1]	A. Arnold, Sequential Monte Carlo Parameter Estimation for Differential Equations,, Ph.D thesis, (2014).
[2]	A. Arnold, D. Calvetti and E. Somersalo, Linear multistep methods, particle filtering and sequential Monte Carlo,, Inverse Problems, 29 (2013).
[3]	O. Brun, V. Teuliere and J.-M. Garcia, Parallel particle filtering,, Journal of Parallel and Distributed Computing, 62 (2002), 1186.
[4]	B. Calderhead, M. Girolami and N. D. Lawrence, Accelerating Bayesian inference over nonlinear differential equations with Gaussian processes,, Adv. Neural Inf. Process. Syst., 21 (2009), 217.
[5]	D. Calvetti and E. Somersalo, Large scale statistical parameter estimation in complex systems with an application to metabolic models,, Multiscale Model. Simul., 5 (2006), 1333.
[6]	N. Chopin, P. E. Jacob and O. Papaspiliopoulos, SMC$^2$: an efficient algorithm for sequential analysis of state space models,, J. R. Stat. Soc. Ser. B Stat. Methodol., 75 (2013), 397.
[7]	A. Golightly and D. J. Wilkinson, Bayesian parameter inference for stochastic biochemical network models using particle MCMC,, J. R. Soc. Interface Focus, 1 (2011), 807.
[8]	A. Iserles, A First Course in the Numerical Analysis of Differential Equations,, $2^{nd}$ edition, (2009).
[9]	A. Lee, C. Yau, M. B. Giles, A. Doucet and C. C. Holmes, On the utility of graphics cards to perform massively parallel simulation of advanced Monte Carlo methods,, J. Comput. Graph. Statist., 19 (2010), 769.
[10]	R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations,, SIAM, (2007).
[11]	C. Lieberman and K. Willcox, Goal-oriented inference: approach, linear theory, and application to advection diffusion,, SIAM Review, 55 (2013), 493.
[12]	J. Liu and M. West, Combined parameter and state estimation in simulation-based filtering,, in Sequential Monte Carlo Methods in Practice* (eds. A. Doucet*, (2001), 197.
[13]	S. Maskell, B. Alun-Jones and M. Macleod, A single instruction multiple data particle filter,, Nonlinear Statistical Signal Processing Workshop 2006 IEEE, (2006), 51.
[14]	L. M. Murray, Bayesian state-space modelling on high-performance hardware using LibBi, preprint,, , ().
[15]	M. Pitt and N. Shephard, Filtering via simulation: auxiliary particle filters,, J. Amer. Statist. Assoc., 94 (1999), 590.
[16]	R. Ren and G. Orkoulas, Parallel Markov chain Monte Carlo simulations,, The Journal of Chemical Physics, 126 (2007).
[17]	L. R. Scott, T. Clark and B. Bagheri, Scientific Parallel Computing,, Princeton, (2005).
[18]	M. West, Approximating posterior distributions by mixtures,, J. R. Stat. Soc. Ser. B Stat. Methodol., 55 (1993), 409.
[19]	M. West, Mixture models, Monte Carlo, Bayesian updating and dynamic models,, in Computing Science and Statistics: Proceedings of the 24th Symposium on the Interface* (ed. J. H. Newton)*, (1993), 325.
[20]	D. J. Wilkinson, Parallel Bayesian computation,, in Handbook of Parallel Computing and Statistics* (ed. E. J. Kontoghiorghes)*, (2005), 477.
[21]	Y. Zhou, vSMC: Parallel sequential Monte Carlo in C++, preprint,, , ().

[1]	Olli-Pekka Tossavainen, Daniel B. Work. Markov Chain Monte Carlo based inverse modeling of traffic flows using GPS data. Networks & Heterogeneous Media, 2013, 8 (3) : 803-824. doi: 10.3934/nhm.2013.8.803
[2]	Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems & Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81
[3]	Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic & Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291
[4]	Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
[5]	Jiakou Wang, Margaret J. Slattery, Meghan Henty Hoskins, Shile Liang, Cheng Dong, Qiang Du. Monte carlo simulation of heterotypic cell aggregation in nonlinear shear flow. Mathematical Biosciences & Engineering, 2006, 3 (4) : 683-696. doi: 10.3934/mbe.2006.3.683
[6]	Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-23. doi: 10.3934/dcdsb.2018335
[7]	Joseph Nebus. The Dirichlet quotient of point vortex interactions on the surface of the sphere examined by Monte Carlo experiments. Discrete & Continuous Dynamical Systems - B, 2005, 5 (1) : 125-136. doi: 10.3934/dcdsb.2005.5.125
[8]	Chjan C. Lim, Joseph Nebus, Syed M. Assad. Monte-Carlo and polyhedron-based simulations I: extremal states of the logarithmic N-body problem on a sphere. Discrete & Continuous Dynamical Systems - B, 2003, 3 (3) : 313-342. doi: 10.3934/dcdsb.2003.3.313
[9]	Mazyar Zahedi-Seresht, Gholam-Reza Jahanshahloo, Josef Jablonsky, Sedighe Asghariniya. A new Monte Carlo based procedure for complete ranking efficient units in DEA models. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 403-416. doi: 10.3934/naco.2017025
[10]	Samuel N. Cohen, Lukasz Szpruch. On Markovian solutions to Markov Chain BSDEs. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 257-269. doi: 10.3934/naco.2012.2.257
[11]	Per Christian Moan, Jitse Niesen. On an asymptotic method for computing the modified energy for symplectic methods. Discrete & Continuous Dynamical Systems - A, 2014, 34 (3) : 1105-1120. doi: 10.3934/dcds.2014.34.1105
[12]	Thomas Schuster, Joachim Weickert. On the application of projection methods for computing optical flow fields. Inverse Problems & Imaging, 2007, 1 (4) : 673-690. doi: 10.3934/ipi.2007.1.673
[13]	Timothy Blass, Rafael de la Llave. Perturbation and numerical methods for computing the minimal average energy. Networks & Heterogeneous Media, 2011, 6 (2) : 241-255. doi: 10.3934/nhm.2011.6.241
[14]	Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing. Journal of Industrial & Management Optimization, 2014, 10 (1) : 113-129. doi: 10.3934/jimo.2014.10.113
[15]	Jingzhi Tie, Qing Zhang. An optimal mean-reversion trading rule under a Markov chain model. Mathematical Control & Related Fields, 2016, 6 (3) : 467-488. doi: 10.3934/mcrf.2016012
[16]	Ralf Banisch, Carsten Hartmann. A sparse Markov chain approximation of LQ-type stochastic control problems. Mathematical Control & Related Fields, 2016, 6 (3) : 363-389. doi: 10.3934/mcrf.2016007
[17]	Kun Fan, Yang Shen, Tak Kuen Siu, Rongming Wang. On a Markov chain approximation method for option pricing with regime switching. Journal of Industrial & Management Optimization, 2016, 12 (2) : 529-541. doi: 10.3934/jimo.2016.12.529
[18]	Dietmar Szolnoki. Set oriented methods for computing reachable sets and control sets. Discrete & Continuous Dynamical Systems - B, 2003, 3 (3) : 361-382. doi: 10.3934/dcdsb.2003.3.361
[19]	Anca-Voichita Matioc. On particle trajectories in linear deep-water waves. Communications on Pure & Applied Analysis, 2012, 11 (4) : 1537-1547. doi: 10.3934/cpaa.2012.11.1537
[20]	Lars Grüne, Vryan Gil Palma. Robustness of performance and stability for multistep and updated multistep MPC schemes. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4385-4414. doi: 10.3934/dcds.2015.35.4385

Impact Factor:

American Institute of Mathematical Sciences