
first numerical example they analyze a stochastic optimal growth model with the parallelization
approach (i) which results in 2,401 problems with 2,401 Chebyshev nodes each – i.e., one rather
large problem per worker. A second numerical example is a dynamic portfolio choice model with
transactions costs, for which they use the parallelization approach (ii). This yields 25 maximization
problems with 3,125 tasks, each task assigned to a worker by the master-worker pattern. For both
problems, they report a parallel efficiency of over 90% for up to 200 workers with regard to one
worker.
Alternatively, sophisticated numerical methods can be used to break the curse of dimensionality.
A general study on breaking the curse of dimensionality for Markovian decision problems, which
includes a comprehensive description of the computer science point of view on approximation
5
algorithms, is written by Rust (1997). Among the first to employ Smolyak’s algorithm for high
dimensional interpolation in an economic model are Krueger and Kubler (2004). They approximate
the unknown equilibrium asset demand functions by global polynomials on sparse grids. Judd et al.
(2014) also use global polynomial interpolation on Smolyak sparse grids and apply these to time and
fixed point iterations to solve for optimal choices in a standard representative agent neoclassical
stochastic growth model, as well as a a multicountry model. Winschel and Kr¨atzig (2010) apply
sparse grids to the interpolation of the policy function using global polynomials, to the quadrature
of integrals arising when computing expectations, and to nonlinear state space filters in a Bayesian
estimation of structural non-linear dynamic economic models. As an application they also analyze
the multicountry model as it allows to vary the number of countries, i.e., the dimensionality of
the problem. They measure runtime, convergence (using unit-free Euler equation errors) and the
number of grid points used in the approximation of the policy functions.
A combination of parallelization and sophisticated numerical methods is done by Brumm and
Scheidegger (2016). They solve economic problems with dynamic programming using a value
function iteration on spatially adaptive sparse grids with local linear basis functions. Their
parallelization uses multiple CPUs to solve for every grid point and GPUs to compute the policy
at every grid point. They run their hybrid parallelization on Piz Daint — a Cray XC30, at the
time this study was written the fastest supercomputer in Europe with 115,984 cores and 73,808
accelerator cards (such as GPUs). Brumm and Scheidegger (2016) report strong scaling results that
show a very good parallel efficiency when the ratio of the number of grid points to the compute
nodes available is large.
A comprehensive discussion of MATLAB’s parallel programming features, design aspects
and implemented parallelization paradigms — such as MPI-based parallelization that allows for
communication of parallel MATLAB sessions — and easy-to-use constructs, such as
parfor
, has
been written by Sharma and Martin (2009).
3 Discrete time dynamic programming
In discrete time dynamic portfolio choice models the individual seeks to maximize expected utility
from her choices (consumption and possibly other endogenous decision variables such as labor
supply) over a finite time horizon. Neglecting boundary and budget constraints for simplicity, this
problem can be expressed through the Bellman equation for a value function
j
t
at a discrete point
5
The terms approximation and interpolation are synonymously used within this paper.
6