Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 44 (2010) no. 1, p. 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]n 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 ε 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.

DOI : https://doi.org/10.1051/m2an/2009039
Classification:  47A20,  65F50,  65N12,  65Y20,  68Q25,  45K05,  65N30
Keywords: wavelet compression, sparse grids, anisotropic integrodifferential operators, norm equivalences
@article{M2AN_2010__44_1_33_0,
     author = {Reich, Nils},
     title = {Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {1},
     year = {2010},
     pages = {33-73},
     doi = {10.1051/m2an/2009039},
     zbl = {1189.65311},
     mrnumber = {2647753},
     language = {en},
     url = {http://www.numdam.org/item/M2AN_2010__44_1_33_0}
}
Reich, Nils. Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 44 (2010) no. 1, pp. 33-73. doi : 10.1051/m2an/2009039. http://www.numdam.org/item/M2AN_2010__44_1_33_0/

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

[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 1137.91421

[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 0983.60028

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

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

[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 0954.65078

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

[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 0980.65130

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

[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 1052.91043

[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 1101.47059

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

[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 0826.65093

[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 0847.65081

[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 0922.42021

[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 1113.65114

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

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

[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 1072.91019

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

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

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

[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 1137.91446

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

[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 1115.41023

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

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

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

[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 1117.65162

[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 1195.91175

[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 0108.09301

[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 0601.35001

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

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

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

[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 1072.60052

[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 1134.91450

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

[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 1154.91473

[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. | Zbl 1189.65311

[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 1177.60069

[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 0973.60001

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

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

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

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

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

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

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

[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 1050.65134

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

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

[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.