Parallelized Dimensional Decomposition for Large-Scale Dynamic Stochastic Economic Models

ABSTRACT

We introduce and deploy a generic, highly scalable computational method to solve high-dimensional dynamic stochastic economic models on high-performance computing platforms. Within an MPI---TBB parallel, nonlinear time iteration framework, we approximate economic policy functions using an adaptive sparse grid algorithm with d-linear basis functions that is combined with a dimensional decomposition scheme. Numerical experiments on "Piz Daint" (Cray XC30) at the Swiss National Supercomputing Centre show that our framework scales nicely to at least 1,000 compute nodes. As an economic application, we compute global solutions to international real business cycle models up to 200 continuous dimensions with significant speedup values over state-of-the-art techniques.

References

1. Ivo Babuška, Fabio Nobile, and Raúl Tempone. 2007. A stochastic collocation method for elliptic partial differential equations with random input data. SIAM J. Numer. Anal. 45, 3 (2007), 1005--1034.
2. Richard E. Bellman. 1961. Adaptive Control Processes: A Guided Tour. Princeton University Press. http://books.google.ch/books?id=POAmAAAAMAAJ
3. Johannes Brumm, Michael Grill, Felix Kubler, and Karl Schmedders. 2015. Collateral requirements and asset prices. International Economic Review 56, 1 (2015), 1--25.
4. Johannes Brumm, Felix Kubler, and Simon Scheidegger. 2016. Computing equilibria in dynamic stochastic macro-models with heterogeneous agents. Advances in Economics and Econometrics, Eleventh World Congress, Forthcoming (2016).
5. Johannes Brumm, Dmitry Mikushin, Simon Scheidegger, and Olaf Schenk. 2015. Scalable high-dimensional dynamic stochastic economic modeling. Journal of Computational Science 11 (2015), 12--25.
6. Johannes Brumm and Simon Scheidegger. 2015. Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models. Working Paper (2015), 1--39.
7. H. J. Bungartz and S. Dirnstorfer. 2003. Multivariate Quadrature on Adaptive Sparse Grids. Computing (Vienna/New York) 71, 1 (2003), 89--114.
8. Hans-Joachim Bungartz and Michael Griebel. 2004. Sparse grids. Acta Numerica 13 (2004), 147--270.
9. Axel BÃűrsch-Supan, Alexander Ludwig, and Joachim Winter. 2006. Ageing, Pension Reform and Capital Flows: A Multi-Country Simulation Model. Economica 73, 292 (2006), 625--658.
10. J J Dongarra and A J van der Steen. 2012. High-performance computing systems: Status and outlook. Acta Numerica 21 (2012), 379--474.
11. Jesús Fernández-Villaverde, Grey Gordon, Pablo Guerrón-Quintana, and Juan F Rubio-Ramirez. 2015. Nonlinear adventures at the zero lower bound. Journal of Economic Dynamics and Control 57 (2015), 182--204.
12. Jochen Garcke. 2012. Sparse Grids and Applications. (2012), 293.
13. William Gropp, Ewing Lusk, and Anthony Skjellum. Using MPI: portable parallel programming with the Message-Passing-Interface.
14. Max Gunzburger, Clayton G. Webster, and Guannan Zhang. 2014. An Adaptive Wavelet Stochastic Collocation Method for Irregular Solutions of Partial differential Equations with Random Input Data. Springer, Cham, 137--170.
15. Wouter J. Den Haan, Kenneth L. Judd, and Michel Juillard. 2011. Computational suite of models with heterogeneous agents II: Multi-country real business cycle models. Journal of Economic Dynamics and Control 35, 2 (2011), 175--177. Computational Suite of Models with Heterogeneous Agents II: Multi-Country Real Business Cycle Models.
16. Markus Hegland. 2003. Adaptive sparse grids. Anziam Journal 44 (2003), 335--353.
17. Markus Holtz. 2010. Sparse Grid Quadrature in High Dimensions with Applications in Finance and Insurance. Lecture Notes in Computational Science and Engineering 77 (2010), 1--192.
18. Giles Hooker. 2007. Generalized Functional ANOVA Diagnostics for High-Dimensional Functions of Dependent Variables. Journal of Computational and Graphical Statistics 16, March (2007), 709--732.
19. John D Jakeman and Stephen G Roberts. 2012. Local and dimension adaptive stochastic collocation for uncertainty quantification. In Sparse grids and applications. Springer Berlin Heidelberg, 181--203.
20. Kenneth Judd. 1992. Projection methods for solving aggregate growth models. Journal of Economic Theory 58, 2 (1992), 410--452. http://econpapers.repec.org/RePEc:eee:jetheo:v:58:y:1992:i:2:p:410-452
21. Kenneth L Judd. 1998. Numerical methods in economics. Vol. 1. The MIT press.
22. Aubhik Khan and Julia K Thomas. 2013. Credit Shocks and Aggregate Fluctuations in an Economy with Production Heterogeneity. Journal of Political Economy 121, 6 (2013), 1055--1107.
23. Robert Kollmann, Serguei Maliar, Benjamin A. Malin, and Paul Pichler. 2011. Comparison of solutions to the multi-country Real Business Cycle model. Journal of Economic Dynamics and Control 35, 2 (2011), 186--202.
24. Dirk Krueger and Alexander Ludwig. 2007. On the consequences of demographic change for rates of returns to capital, and the distribution of wealth and welfare. Journal of Monetary Economics 54, 1 (2007), 49--87. http://EconPapers.repec.org/RePEc:eee:moneco:v:54:y:2007:i:1:p:49-87
25. Dirk Krüger and Felix Kubler. 2004. Computing equilibrium in OLG models with stochastic production. Journal of Economic Dynamics and Control 28, 7 (2004), 1411--1436.
26. F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, and H. Woźniakowski. 2009. On decompositions of multivariate functions. Math. Comp. 79, 270 (2009), 953--966.
27. Genyuan Li and Herschel Rabitz. 2012. General formulation of HDMR component functions with independent and correlated variables. Journal of Mathematical Chemistry 50, 1 (2012), 99--130.
28. G Li, Sw Wang, and H Rabitz. 2000. High Dimensional Model Representations (HDMR): Concepts and applications. (2000).
29. Lars Ljungqvist and Thomas J Sargent. 2004. Recursive macroeconomic theory. Mit Press.
30. Xiang Ma and Nicholas Zabaras. 2009. An adaptive hierarchical sparse grid collocation algorithm for the solution of stochastic differential equations. J. Comput. Phys. 228, 8 (2009), 3084--3113.
31. Xiang Ma and Nicholas Zabaras. 2010. An adaptive high-dimensional stochastic model representation technique for the solution of stochastic partial differential equations. J. Comput. Phys. 229, 10 (2010), 3884--3915.
32. Lilia Maliar and Serguei Maliar. 2014. Chapter 7 - Numerical Methods for Large-Scale Dynamic Economic Models. In Handbook of Computational Economics Vol. 3, Karl Schmedders and Kenneth L. Judd (Eds.). Handbook of Computational Economics, Vol. 3. Elsevier, 325--477.
33. Lilia Maliar and Serguei Maliar. 2015. Merging simulation and projection approaches to solve high-dimensional problems with an application to a new Keynesian model. Quantitative Economics 6, 1 (2015), 1--47.
34. Alin Murarasu, Josef Weidendorfer, Gerrit Buse, Daniel Butnaru, and Dirk Pflüeger. 2011. Compact Data Structure and Parallel Alogrithms for the Sparse Grid Technique. In 16th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.
35. Fabio Nobile, Raúl Tempone, and Clayton G Webster. 2008. A sparse grid stochastic collocation method for partial differential equations with random input data. SIAM J. Numer. Anal. 46, 5 (2008), 2309--2345.
36. Dirk Pflüger. 2010. Spatially Adaptive Sparse Grids for High-Dimensional Problems. 1--194 pages. http://www5.in.tum.de/pub/pflueger10spatially.pdf
37. Herschel Rabitz, ÃŰ Alis, and ÃŰmer F. AlÄśş. 1999. General foundations of high-dimensional model representations. J. Math. Chem. 25, 2--3 (1999), 197--233.
38. Sharif Rahman. 2014. A Generalized ANOVA Dimensional Decomposition for Dependent Probability Measures. arXiv:1408.0722v1 {math.NA} 52242 (2014), 27. http://arxiv.org/abs/1408.0722
39. James. Reinders and James. 2007. Intel threading building blocks: outfitting C++ for multi-core processor parallelism. O'Reilly. 303 pages.
40. Serdar Sayan. 2005. HeckscherâĂŞOhlin revisited: implications of differential population dynamics for trade within an overlapping generations framework. Journal of Economic Dynamics and Control 29, 9 (2005), 1471--1493.
41. Simon Scheidegger and Adrien Treccani. 2016. Pricing American Options Under High-Dimensional Models with Recursive Adaptive Sparse Expectations. Available at SSRN 2867926 (2016).
42. I. M. Sobol. 2003. Theorems and examples on high dimensional model representation. Reliability Engineering & System Safety 79, 2 (2003), 187--193.
43. Nancy Stokey, Robert Lucas, and Edward Prescott. 1989. Recursive methods in economic dynamics. Cambridge MA (1989).
44. Harald Uhlig. 1995. A toolkit for analyzing nonlinear dynamic stochastic models easily. Technical Report.
45. Andreas Wächter, Âů Lorenz, and T Biegler. 2005. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program., Ser. A (2005).
46. X. Wang. 2008. On the approximation error in high dimensional model representation. Proceedings of the 2008 Winter Simulation Conference 1 (2008), 453--462.
47. Xiu Yang, Minseok Choi, Guang Lin, and George Em Karniadakis. 2012. Adaptive ANOVA decomposition of stochastic incompressible and compressible flows. J. Comput. Phys. 231, 4 (2012), 1587--1614.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics

• Computing methodologies

  • Distributed computing methodologies

    • Distributed algorithms

  • Modeling and simulation