Error analysis of truncated expansion solutions to high-dimensional parabolic PDEs

Reisinger, Christoph; Wissmann, Rasmus

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 51 (2017) no. 6, pp. 2435-2463.

We study an expansion method for high-dimensional parabolic PDEs which constructs accurate approximate solutions by decomposition into solutions to lower-dimensional PDEs, and which is particularly effective if there are a low number of dominant principal components. The focus of the present article is the derivation of sharp error bounds for the constant coefficient case and a first and second order approximation. We give a precise characterisation when these bounds hold for (non-smooth) option pricing applications and provide numerical results demonstrating that the practically observed convergence speed is in agreement with the theoretical predictions.

P.L.T. Brian, A finite-difference method of higher-order accuracy for the solution of three-dimensional transient heat conduction problems. AIChE J. 7 (1961) 367–370. | DOI

H.-J. Bungartz and M. Griebel, Sparse grids. Acta Numer. 13 (2004) 1–123. | MR | Zbl

M.J. Chang, L.C. Chow and W.S. Chang, Improved alternating-direction implicit method for solving transient three-dimensional heat diffusion problems. Numer. Heat Trans. Part B: Fundamentals 19 (1991) 69–84. | DOI

L.C. Evans, Partial Differential Equations. AMS, Providence, 1st edition (2000). | MR | Zbl

T. Gerstner and M. Griebel. Dimension-adaptive tensor-product quadrature. Comput. 71 (2003) 65–87. | DOI | MR | Zbl

L. Grasedyck, D. Kressner and C. Tobler, A literature survey of low-rank tensor approximation techniques. GAMM-Mitteilungen 36 (2013) 53–78. | DOI | MR | Zbl

M. Griebel and M. Holtz, Dimension-wise integration of high-dimensional functions with applications to finance. J. Complex. 26 (2010) 455–489. | DOI | MR | Zbl

M. Griebel and A. Hullmann, Dimensionality reduction of high-dimensional data with a nonlinear principal component aligned generative topographic mapping. SIAM J. Sci. Comput. 36 (2014) 1027–1047. | DOI | MR | Zbl

M. Griebel, F.Y. Kuo and I.H. Sloan, The smoothing effect of the ANOVA decomposition. J. Complex. 26 (2010) 523–551. | DOI | MR | Zbl

L.G. Gyurko and T. Lyons, Efficient and practical implementations of cubature on Wiener space. In Stoch. Anal.. Springer (2011) 73–111. | MR | Zbl

T. Haentjens and K.J. in ‘t Hout, ADI finite difference discretization of the Heston-Hull-White PDE. In Vol. 1281 of ICNAAM 2010: International Conference of Numerical Analysis and Applied Mathematics 2010. AIP Publishing (2010) 1995–1999.

A. Heinecke, S. Schraufstetter and H.-J. Bungartz, A highly parallel Black-Scholes solver based on adaptive sparse grids. Int. J. Comput. Math. 89 (2012) 1212–1238. | DOI | MR | Zbl

N. Hilber, S. Kehtari, C. Schwab and C. Winter, Wavelet finite element method for option pricing in highdimensional diffusion market models. Technical Report 2010–01, SAM, ETH Zürich (2010).

J. Imai and K.S. Tan, Minimizing effective dimension using linear transformation. In Monte Carlo and Quasi-Monte Carlo Methods 2002. Springer (2004). 275–292 | MR | Zbl

K.J. In ‘T Hout and S. Foulon, ADI finite difference schemes for option pricing in the Heston model with correlation. Int. J. Numer. Anal. Model. 7 (2010) 303–320. | MR | Zbl

R. Sircar J.-P. Fouque, G. Papanicolaou and K. Sølna, Multiscale stochastic volatility for equity, interest rate, and credit derivatives. Cambridge University Press (2011). | MR | Zbl

V. Kazeev, O. Reichmann and C. Schwab, Low-rank tensor structure of linear diffusion operators in the TT and QTT formats. Lin. Algebra Appl. 438 (2013) 4204–4221. | DOI | MR | Zbl

K. Königsberger, Analysis 2. Springer (2004). | Zbl

F.Y. Kuo, I.H. Sloan, G.W. Wasilkowski and H. Wozniakowski, On decompositions of multivariate functions. Math. Comput. 79 (2010) 953–966. | DOI | MR | Zbl

C.C.W. Leentvaar and C.W. Oosterlee, On coordinate transformation and grid stretching for sparse grid pricing of basket options. J. Comput. Appl. Math. 222 (2008) 193–209. | DOI | MR | Zbl

S.K. Lele, Compact finite difference schemes with spectral-like resolution. J. Comput. Phys. 103 (1992) 16–42. | DOI | MR | Zbl

C. Litterer and T. Lyons, High order recombination and an application to cubature on Wiener space. Ann. Appl. Prob. 22 (2012) 1301–1327. | DOI | MR | Zbl

T. Lyons and N. Victoir, Cubature on Wiener space. Proc. Royal Soc. A 460 (2004) 169–198. | DOI | MR | Zbl

D.W. Peaceman and H.H. Rachford, Jr. The numerical solution of parabolic and elliptic differential equations. J. Soc. Ind. Appl. Math. 3 (1955) 28–41. | DOI | MR | Zbl

U. Pettersson, E. Larsson, G. Marcusson and J. Persson, Improved radial basis function methods for multi-dimensional option pricing. J. Comput. Appl. Math. 222 (2008) 82–93. | DOI | MR | Zbl

C. Reisinger, Asymptotic expansion around principal components and the complexity of dimension adaptive algorithms. In Sparse Grids and Applications, edited by J. Garcke and M. Griebel. Vol. 88 of Springer Lectures Notes in Computational Science and Engineering (2012) 263–276. | MR

C. Reisinger and R. Wissmann, Numerical valuation of derivatives in high-dimensional settings via PDE expansions. J. Comput. Fin. 18 (2015).

C. Reisinger and R. Wissmann, Finite difference methods for medium- and high-dimensional derivative pricing PDEs. In High-Performance Computing in Finance: Problems, Methods, and Solutions, edited by E. Vynckier, J. Kanniainen and J. Keane. Chapman and Hall/CRC, London (2017).

C. Reisinger and G. Wittum, Efficient hierarchical approximation of high-dimensional option pricing problems. SIAM J. Sci. Comput. 29 (2007) 440–458. | DOI | MR | Zbl

P. Schröder, T. Gerstner and G. Wittum, Taylor-like ANOVA-expansion for high dimensional problems in finance. Working paper (2012).

P. Schröder, P. Mlynczak and G. Wittum, Dimension-wise decompositions and their efficient parallelization. In edited by T Gerstner and P.E. Kloeden. Recent Developments in Computational Finance: Foundations, Algorithms and Applications. Vol. 14 of Interdisciplinary Mathematical Sciences. World Scientific (2013). | MR | Zbl

I.H. Sloan, F.Y. Kuo and S. Joe, Constructing randomly shifted lattice rules in weighted Sobolev spaces. SIAM J. Numer. Anal. 40 (2002) 1650–1665. | DOI | MR | Zbl

I.H. Sloan, F.Y. Kuo and S. Joe, On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces. Math. Comput. 71 (2002) 1609–1640. | DOI | MR | Zbl

T. Von Petersdorff and C. Schwab, Numerical solution of parabolic equations in high dimensions. ESAIM: M2AN 38 (2004) 93–127. | DOI | Numdam | MR | Zbl

X. Wang, On the approximation error in high dimensional model representation. Edited by S.J. Mason, R.R. Hill, L. Mönch, O. Rose, T. Jefferson and J.W. Fowle. Winter Simulation Conference 2008 (2008) 453–462.

X. Wang and I.H. Sloan, Why are high-dimension finance problems often of low effective dimension? SIAM J. Sci. Comput. 27 (2005) 159–183. | DOI | MR | Zbl

R. Wissmann, Expansion methods for high-dimensional PDEs in finance. DPhil thesis, University of Oxford (2015).

Z. Zhang, M. Choi and G.E.M. Karniadakis, Error estimates for the ANOVA method with polynomial chaos interpolation: tensor product functions. SIAM J. Sci. Comput. 34 (2012) 1165–1186. | DOI | MR | Zbl

Y.-L. Zhu and J. Li, Multi-factor financial derivatives on finite domains. Commun. Math. Sci. 1 (2003) 343–359. | DOI | MR | Zbl