American Institute of Mathematical Sciences

Advanced
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

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, Case Western Reserve University, 2014.

[2]

A. Arnold, D. Calvetti and E. Somersalo, Linear multistep methods, particle filtering and sequential Monte Carlo, Inverse Problems, 29 (2013), 085007.

[3]

O. Brun, V. Teuliere and J.-M. Garcia, Parallel particle filtering, Journal of Parallel and Distributed Computing, 62 (2002), 1186-1202.

[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-224.

[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-1366.

[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-426.

[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-820.

[8]

A. Iserles, A First Course in the Numerical Analysis of Differential Equations, $2^{nd}$ edition, Cambridge Texts in Applied Mathematics, Cambridge University Press, New York, 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-789.

[10]

R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations, SIAM, Philadelphia, 2007.

[11]

C. Lieberman and K. Willcox, Goal-oriented inference: approach, linear theory, and application to advection diffusion, SIAM Review, 55 (2013), 493-519.

[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, J. F. G. de Freitas and N. J. Gordon), Springer, New York (2001), 197-223.

[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-54.

[14]

L. M. Murray, Bayesian state-space modelling on high-performance hardware using LibBi, preprint, arXiv:1306.3277.

[15]

M. Pitt and N. Shephard, Filtering via simulation: auxiliary particle filters, J. Amer. Statist. Assoc., 94 (1999), 590-599.

[16]

R. Ren and G. Orkoulas, Parallel Markov chain Monte Carlo simulations, The Journal of Chemical Physics, 126 (2007), 211102.

[17]

L. R. Scott, T. Clark and B. Bagheri, Scientific Parallel Computing, Princeton, Princeton, NJ, 2005.

[18]

M. West, Approximating posterior distributions by mixtures, J. R. Stat. Soc. Ser. B Stat. Methodol., 55 (1993), 409-422.

[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), Interface Foundation of America, Fairfax Station, VA (1993), 325-333.

[20]

D. J. Wilkinson, Parallel Bayesian computation, in Handbook of Parallel Computing and Statistics (ed. E. J. Kontoghiorghes), Chapman & Hall/CRC, Boca Raton, FL (2005), 477-508.

[21]

Y. Zhou, vSMC: Parallel sequential Monte Carlo in C++, preprint, arXiv:1306.5583.

show all references

References:
[1]

A. Arnold, Sequential Monte Carlo Parameter Estimation for Differential Equations, Ph.D thesis, Case Western Reserve University, 2014.

[2]

A. Arnold, D. Calvetti and E. Somersalo, Linear multistep methods, particle filtering and sequential Monte Carlo, Inverse Problems, 29 (2013), 085007.

[3]

O. Brun, V. Teuliere and J.-M. Garcia, Parallel particle filtering, Journal of Parallel and Distributed Computing, 62 (2002), 1186-1202.

[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-224.

[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-1366.

[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-426.

[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-820.

[8]

A. Iserles, A First Course in the Numerical Analysis of Differential Equations, $2^{nd}$ edition, Cambridge Texts in Applied Mathematics, Cambridge University Press, New York, 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-789.

[10]

R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations, SIAM, Philadelphia, 2007.

[11]

C. Lieberman and K. Willcox, Goal-oriented inference: approach, linear theory, and application to advection diffusion, SIAM Review, 55 (2013), 493-519.

[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, J. F. G. de Freitas and N. J. Gordon), Springer, New York (2001), 197-223.

[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-54.

[14]

L. M. Murray, Bayesian state-space modelling on high-performance hardware using LibBi, preprint, arXiv:1306.3277.

[15]

M. Pitt and N. Shephard, Filtering via simulation: auxiliary particle filters, J. Amer. Statist. Assoc., 94 (1999), 590-599.

[16]

R. Ren and G. Orkoulas, Parallel Markov chain Monte Carlo simulations, The Journal of Chemical Physics, 126 (2007), 211102.

[17]

L. R. Scott, T. Clark and B. Bagheri, Scientific Parallel Computing, Princeton, Princeton, NJ, 2005.

[18]

M. West, Approximating posterior distributions by mixtures, J. R. Stat. Soc. Ser. B Stat. Methodol., 55 (1993), 409-422.

[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), Interface Foundation of America, Fairfax Station, VA (1993), 325-333.

[20]

D. J. Wilkinson, Parallel Bayesian computation, in Handbook of Parallel Computing and Statistics (ed. E. J. Kontoghiorghes), Chapman & Hall/CRC, Boca Raton, FL (2005), 477-508.

[21]

Y. Zhou, vSMC: Parallel sequential Monte Carlo in C++, preprint, arXiv:1306.5583.

[1]

Ajay Jasra, Kody J. H. Law, Yaxian Xu. Markov chain simulation for multilevel Monte Carlo. Foundations of Data Science, 2021, 3 (1) : 27-47. doi: 10.3934/fods.2021004
[2]

Olli-Pekka Tossavainen, Daniel B. Work. Markov Chain Monte Carlo based inverse modeling of traffic flows using GPS data. Networks and Heterogeneous Media, 2013, 8 (3) : 803-824. doi: 10.3934/nhm.2013.8.803
[3]

Zhiyan Ding, Qin Li. Constrained Ensemble Langevin Monte Carlo. Foundations of Data Science, 2022, 4 (1) : 37-70. doi: 10.3934/fods.2021034
[4]

Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic and Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291
[5]

Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems and Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81
[6]

Theodore Papamarkou, Alexey Lindo, Eric B. Ford. Geometric adaptive Monte Carlo in random environment. Foundations of Data Science, 2021, 3 (2) : 201-224. doi: 10.3934/fods.2021014
[7]

Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
[8]

Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335
[9]

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
[10]

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 and Continuous Dynamical Systems - B, 2003, 3 (3) : 313-342. doi: 10.3934/dcdsb.2003.3.313
[11]

Joseph Nebus. The Dirichlet quotient of point vortex interactions on the surface of the sphere examined by Monte Carlo experiments. Discrete and Continuous Dynamical Systems - B, 2005, 5 (1) : 125-136. doi: 10.3934/dcdsb.2005.5.125
[12]

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 and Optimization, 2017, 7 (4) : 403-416. doi: 10.3934/naco.2017025
[13]

Samuel N. Cohen, Lukasz Szpruch. On Markovian solutions to Markov Chain BSDEs. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 257-269. doi: 10.3934/naco.2012.2.257
[14]

Ying Liu, Yabing Sun, Weidong Zhao. Explicit multistep stochastic characteristic approximation methods for forward backward stochastic differential equations. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 773-795. doi: 10.3934/dcdss.2021044
[15]

Per Christian Moan, Jitse Niesen. On an asymptotic method for computing the modified energy for symplectic methods. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 1105-1120. doi: 10.3934/dcds.2014.34.1105
[16]

Thomas Schuster, Joachim Weickert. On the application of projection methods for computing optical flow fields. Inverse Problems and Imaging, 2007, 1 (4) : 673-690. doi: 10.3934/ipi.2007.1.673
[17]

Timothy Blass, Rafael de la Llave. Perturbation and numerical methods for computing the minimal average energy. Networks and Heterogeneous Media, 2011, 6 (2) : 241-255. doi: 10.3934/nhm.2011.6.241
[18]

Takeshi Saito, Kazuyuki Yagasaki. Chebyshev spectral methods for computing center manifolds. Journal of Computational Dynamics, 2021, 8 (2) : 165-181. doi: 10.3934/jcd.2021008
[19]

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 and Management Optimization, 2014, 10 (1) : 113-129. doi: 10.3934/jimo.2014.10.113
[20]

Anca-Voichita Matioc. On particle trajectories in linear deep-water waves. Communications on Pure and Applied Analysis, 2012, 11 (4) : 1537-1547. doi: 10.3934/cpaa.2012.11.1537

 Impact Factor: 

Tools

Metrics

  • PDF downloads (76)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy