Efficient spectral sparse grid approximations for solving multi-dimensional forward backward SDEs

This is the second part of a series papers on multi-step schemes for solving coupled forward backward stochastic differential equations (FBSDEs). We extend the basic idea in our former paper [W. Zhao, Y. Fu and T. Zhou, SIAM J. Sci. Comput., 36 (2014), pp. A1731-A1751] to solve high-dimensional FBSDEs, by using the spectral sparse grid approximations. The main issue for solving high-dimensional FBSDEs is to build an efficient spatial discretization, and deal with the related high-dimensional conditional expectations and interpolations. In this work, we propose the sparse grid spatial discretization. The sparse grid Gaussian-Hermite quadrature rule is used to approximate the conditional expectations. And for the associated high-dimensional interpolations, we adopt a spectral expansion of functions in polynomial spaces with respect to the spatial variables, and use the sparse grid approximations to recover the expansion coefficients. The FFT algorithm is used to speed up the recovery procedure, and the entire algorithm admits efficient and highly accurate approximations in high dimensions. Several numerical examples are presented to demonstrate the efficiency of the proposed methods.