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, (2014).   Google Scholar

[2]

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

[3]

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

[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.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[8]

A. Iserles, A First Course in the Numerical Analysis of Differential Equations,, $2^{nd}$ edition, (2009).   Google Scholar

[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.   Google Scholar

[10]

R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations,, SIAM, (2007).   Google Scholar

[11]

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

[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.   Google Scholar

[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.   Google Scholar

[14]

L. M. Murray, Bayesian state-space modelling on high-performance hardware using LibBi, preprint,, , ().   Google Scholar

[15]

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

[16]

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

[17]

L. R. Scott, T. Clark and B. Bagheri, Scientific Parallel Computing,, Princeton, (2005).   Google Scholar

[18]

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

[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.   Google Scholar

[20]

D. J. Wilkinson, Parallel Bayesian computation,, in Handbook of Parallel Computing and Statistics (ed. E. J. Kontoghiorghes), (2005), 477.   Google Scholar

[21]

Y. Zhou, vSMC: Parallel sequential Monte Carlo in C++, preprint,, , ().   Google Scholar

show all references

References:
[1]

A. Arnold, Sequential Monte Carlo Parameter Estimation for Differential Equations,, Ph.D thesis, (2014).   Google Scholar

[2]

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

[3]

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

[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.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[8]

A. Iserles, A First Course in the Numerical Analysis of Differential Equations,, $2^{nd}$ edition, (2009).   Google Scholar

[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.   Google Scholar

[10]

R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations,, SIAM, (2007).   Google Scholar

[11]

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

[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.   Google Scholar

[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.   Google Scholar

[14]

L. M. Murray, Bayesian state-space modelling on high-performance hardware using LibBi, preprint,, , ().   Google Scholar

[15]

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

[16]

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

[17]

L. R. Scott, T. Clark and B. Bagheri, Scientific Parallel Computing,, Princeton, (2005).   Google Scholar

[18]

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

[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.   Google Scholar

[20]

D. J. Wilkinson, Parallel Bayesian computation,, in Handbook of Parallel Computing and Statistics (ed. E. J. Kontoghiorghes), (2005), 477.   Google Scholar

[21]

Y. Zhou, vSMC: Parallel sequential Monte Carlo in C++, preprint,, , ().   Google Scholar

[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, 2019, 24 (8) : 3881-3903. 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]

Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences