Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces

Reich, Nils

ESAIM: Modélisation mathématique et analyse numérique, Tome 44 (2010) no. 1, pp. 33-73.

For a class of anisotropic integrodifferential operators $ℬ$ arising as semigroup generators of Markov processes, we present a sparse tensor product wavelet compression scheme for the Galerkin finite element discretization of the corresponding integrodifferential equations $ℬ$ u = f on [0,1]ⁿ with possibly large n. Under certain conditions on $ℬ$, the scheme is of essentially optimal and dimension independent complexity $𝒪$(h^-1| log h |^2(n-1)) without corrupting the convergence or smoothness requirements of the original sparse tensor finite element scheme. If the conditions on $ℬ$ are not satisfied, the complexity can be bounded by $𝒪$(h^-(1+ε)), where ε $\ll 1$ tends to zero with increasing number of the wavelets’ vanishing moments. Here h denotes the width of the corresponding finite element mesh. The operators under consideration are assumed to be of non-negative (anisotropic) order and admit a non-standard kernel κ$(·,·)$ that can be singular on all secondary diagonals. Practical examples of such operators from Mathematical Finance are given and some numerical results are presented.

[1] Y. Achdou and O. Pironneau, A numerical procedure for calibration of volatility with American options. Appl. Math. Finance 12 (2005) 201-241. | Zbl

[2] Y. Achdou and N. Tchou, Variational analysis for the Black and Scholes equation with stochastic volatility. ESAIM: M2AN 36 (2002) 373-395. | Numdam | Zbl

[3] O.E. Barndorff-Nielsen and N. Shephard, Non-Gaussian Ornstein-Uhlenbeck-based models and some of their uses in financial economics. J. Roy. Stat. Soc. 63 (2001) 167-241. | Zbl

[4] J. Bertoin, Lévy processes. Cambridge University Press, Cambridge, UK (1996). | Zbl

[5] G. Beylkin, R. Coifman and V. Rokhlin, The fast wavelet transform and numerical algorithms. Comm. Pure Appl. Math. 44 (1991) 141-183. | Zbl

[6] J.H. Bramble, A. Cohen and W. Dahmen, Multiscale problems and methods in numerical simulations, Lecture Notes in Mathematics 1825. Springer-Verlag, Berlin, Germany (2003).

[7] H.-J. Bungartz and M. Griebel, A note on the complexity of solving Poisson's equation for spaces of bounded mixed derivatives. J. Complexity 15 (1999) 167-199. | Zbl

[8] A. Cohen, I. Daubechies and J.-C. Feauveau, Biorthogonal bases of compactly supported wavelets. Comm. Pure Appl. Math. 45 (1992) 485-560. | Zbl

[9] A. Cohen, W. Dahmen and R. Devore, Adaptive wavelet methods for elliptic operator equations: convergence rates. Math. Comp. 70 (2001) 27-75 (electronic). | Zbl

[10] A. Cohen, W. Dahmen and R. Devore, Adaptive wavelet methods. II. Beyond the elliptic case. Found. Comput. Math. 2 (2002) 203-245. | Zbl

[11] R. Cont and P. Tankov, Financial modelling with jump processes. Chapman & Hall/CRC Financial Mathematics Series. Chapman & Hall/CRC, Boca Raton, USA (2004). | Zbl

[12] R. Cont and E. Voltchkova, A finite difference scheme for option pricing in jump diffusion and exponential Lévy models. SIAM J. Numer. Anal. 43 (2005) 1596-1626. | Zbl

[13] W. Dahmen and R. Schneider, Wavelets with complementary boundary conditions - function spaces on the cube. Results Math. 34 (1998) 255-293. | Zbl

[14] W. Dahmen, S. Prössdorf and R. Schneider, Wavelet approximation methods for pseudodifferential equations. II. Matrix compression and fast solution. Adv. Comput. Math. 1 (1993) 259-335. | Zbl

[15] W. Dahmen, S. Prössdorf and R. Schneider, Multiscale methods for pseudo-differential equations on smooth closed manifolds, in Wavelets: theory, algorithms, and applications (Taormina, 1993), Wavelet Anal. Appl. 5, Academic Press, San Diego, USA (1994) 385-424. | Zbl

[16] W. Dahmen, A. Kunoth and K. Urban, Biorthogonal spline wavelets on the interval - stability and moment conditions. Appl. Comput. Harmon. Anal. 6 (1999) 132-196. | Zbl

[17] W. Dahmen, H. Harbrecht and R. Schneider, Compression techniques for boundary integral equations - asymptotically optimal complexity estimates. SIAM J. Numer. Anal. 43 (2006) 2251-2271 (electronic). | Zbl

[18] F. Delbaen and W. Schachermayer, A general version of the fundamental theorem of asset pricing. Math. Ann. 300 (1994) 463-520. | Zbl

[19] F. Delbaen and W. Schachermayer, The variance-optimal martingale measure for continuous processes. Bernoulli 2 (1996) 81-105. | Zbl

[20] F. Delbaen, P. Grandits, T. Rheinländer, D. Samperi, M. Schweizer and C. Stricker, Exponential hedging and entropic penalties. Math. Finance 12 (2002) 99-123. | Zbl

[21] M. Demuth and J. Van Casteren, Stochastic Spectral Theory for Selfadjoint Feller Operators. Birkhäuser Verlag, Basel (2000). | Zbl

[22] R. Devore, Nonlinear approximation, in Acta numerica (1998), Acta Numer. 7, Cambridge Univ. Press, Cambridge, UK (1998) 51-150. | Zbl

[23] A. Ern and J.-L. Guermond, Theory and practice of Finite Elements. Springer Verlag, New York, USA (2004). | Zbl

[24] W. Farkas, N. Reich and C. Schwab, Anisotropic stable Lévy copula processes - analytical and numerical aspects. Math. Models Methods Appl. Sci. 17 (2007) 1405-1443. | Zbl

[25] T. Gantumur and R. Stevenson, Computation of differential operators in wavelet coordinates. Math. Comp. 75 (2006) 697-709 (electronic). | Zbl

[26] T. Gantumur, H. Harbrecht and R. Stevenson, An optimal adaptive wavelet method without coarsening of the iterands. Math. Comp. 76 (2007) 615-629 (electronic). | Zbl

[27] M. Griebel and S. Knapek, Optimized general sparse grid approximation spaces for operator equations. Math. Comp. (to appear). | Zbl

[28] M. Griebel, P. Oswald and T. Schiekofer, Sparse grids for boundary integral equations. Numer. Math. 83 (1999) 279-312. | Zbl

[29] H. Harbrecht and R. Schneider, Biorthogonal wavelet bases for the boundary element method. Math. Nachr. 269/270 (2004) 167-188. | Zbl

[30] H. Harbrecht and R. Schneider, Wavelet Galerkin schemes for boundary integral equations - implementation and quadrature. SIAM J. Sci. Comput. 27 (2006) 1347-1370 (electronic). | Zbl

[31] N. Hilber, A.-M. Matache and C. Schwab, Sparse wavelet methods for option pricing under stochastic volatility. J. Comput. Finance 8 (2005) 1-42.

[32] N. Hilber, N. Reich, C. Schwab and C. Winter, Numerical methods for Lévy processes. Finance Stoch. 13 (2009) 471-500. Special Issue on Computational Methods in Finance (Part II). | Zbl

[33] N. Hilber, N. Reich and C. Winter, Wavelet methods, in Encyclopedia of Quantitative Finance, R. Cont Ed., John Wiley & Sons Ltd., Chichester (to appear).

[34] W. Hoh, Pseudo Differential Operators generating Markov Processes. Habilitationsschrift, University of Bielefeld, Germany (1998).

[35] L. Hörmander, Linear partial differential operators, Grundlehren der Mathematischen Wissenschaften 116 [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, Germany (1963). | Zbl

[36] L. Hörmander, The analysis of linear partial differential operators. III: Pseudodifferential operators, Grundlehren der Mathematischen Wissenschaften 274 [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, Germany (1985). | Zbl

[37] N. Jacob, Pseudo Differential Operators and Markov Processes, Vol. 2: Generators and their potential theory. Imperial College Press, London, UK (2002). | Zbl

[38] N. Jacob, Pseudo Differential Operators and Markov Processes, Vol. 3: Markov processes and applications. Imperial College Press, London, UK (2005). | Zbl

[39] S. Knapek and F. Koster, Integral operators on sparse grids. SIAM J. Numer. Anal. 39 (2001/2002) 1794-1809 (electronic). | Zbl

[40] F. Liu, N. Reich and A. Zhou, Two-scale Finite Element Discretizations for Infinitesimal Generators of Jump Processes in Finance. Research report 2008-23 Seminar for Applied Mathematics, ETH Zürich, Switzerland (2008).

[41] A.-M. Matache, T. Von Petersdorff and C. Schwab, Fast deterministic pricing of options on Lévy driven assets. ESAIM: M2AN 38 (2004) 37-71. | Numdam | Zbl

[42] A.-M. Matache, P.A. Nitsche and C. Schwab, Wavelet Galerkin pricing of American contracts on Lévy driven assets. Quant. Finance 5 (2005) 403-424. | Zbl

[43] H. Nguyen and R. Stevenson, Finite element wavelets on manifolds. IMA J. Numer. Math. 23 (2003) 149-173. | Zbl

[44] P. Oswald, On N-term approximation by Haar functions in Hs-norms, in Metric Function Theory and Related Topics in Analysis, S.M. Nikolskij, B.S. Kashin and A.D. Izaak Eds., AFC, Moscow, Russia (1999) 137-163.

[45] N. Reich, Multiscale analysis for jump processes in finance, in Numerical Mathematics and Advanced Applications, K. Kunisch, G. Of and O. Steinbach Eds., Springer Verlag, Berlin, Germany (2008) 415-422. | Zbl

[46] N. Reich, Wavelet Compression of Anisotropic Integrodifferential Operators on Sparse Tensor Product Spaces. Ph.D. Thesis 17661, ETH Zürich, Switzerland (2008). Available at http://e-collection.ethbib.ethz.ch/view/eth:30174.

[47] N. Reich, Wavelet Compression of Integral Operators on Sparse Tensor Spaces - Construction, Consistency and Asymptotically Optimal Complexity. Research report 2008-24, Seminar for Applied Mathematics, ETH Zürich, Switzerland (2008).

[48] N. Reich, Anisotropic operator symbols arising from multivariate jump processes. Integr. Equ. Oper. Theory 63 (2009) 127-150. | Zbl

[49] N. Reich, C. Schwab and C. Winter, On Kolmogorov equations for anisotropic multivariate Lévy processes. Finance Stoch. (to appear).

[50] K.-I. Sato, Lévy Processes and Infinitely Divisible Distributions. Cambridge University Press, Cambridge, UK (1999). | Zbl

[51] R. Schneider, Multiskalen- und Wavelet-Matrixkompression: Analysisbasierte Methoden zur Lösung großer vollbesetzter Gleichungssysteme. B.G. Teubner, Stuttgart, Germany (1998). | Zbl

[52] C. Schwab and R. Stevenson, Adaptive wavelet algorithms for elliptic PDE's on product domains. Math. Comp. 77 (2008) 71-92 (electronic). | Zbl

[53] R.E. Showalter, Monotone Operators in Banach Space and Nonliner Partial Differential Equations. American Mathematical Society, Rhode Island, USA (1997). | Zbl

[54] E.M. Stein, Harmonic Analysis. Princeton University Press, Princeton, USA (1993). | Zbl

[55] R. Stevenson, On the compressibility of operators in wavelet coordinates. SIAM J. Math. Anal. 35 (2004) 1110-1132 (electronic). | Zbl

[56] M.E. Taylor, Pseudodifferential operators. Princeton University Press, Princeton, USA (1981). | Zbl

[57] H. Triebel, Interpolation theory, function spaces, differential operators. Second edition, Johann Ambrosius Barth Verlag, Heidelberg, Germany (1995). | Zbl

[58] T. Von Petersdorff and C. Schwab, Fully discrete multiscale Galerkin BEM, in Multiscale wavelet methods for PDEs, W. Dahmen, A. Kurdila and P. Oswald Eds., Academic Press, San Diego, USA (1997) 287-346.

[59] T. Von Petersdorff and C. Schwab, Wavelet discretizations of parabolic integrodifferential equations. SIAM J. Numer. Anal. 41 (2003) 159-180 (electronic). | Zbl

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

[61] T. Von Petersdorff, C. Schwab and R. Schneider, Multiwavelets for second-kind integral equations. SIAM J. Numer. Anal. 34 (1997) 2212-2227. | Zbl

[62] C. Winter, Wavelet Galerkin schemes for option pricing in multidimensional Lévy models. Ph.D. Thesis 18221, ETH Zürich, Switzerland (2009). Available at http://e-collection.ethbib.ethz.ch/view/eth:41555.