Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces

Nils Reich

ESAIM: Mathematical Modelling and Numerical Analysis (2010)

  • Volume: 44, Issue: 1, page 33-73
  • ISSN: 0764-583X

Abstract

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

How to cite

top

Reich, Nils. "Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces." ESAIM: Mathematical Modelling and Numerical Analysis 44.1 (2010): 33-73. <http://eudml.org/doc/250788>.

@article{Reich2010,
abstract = { For a class of anisotropic integrodifferential operators $\{\cal B\}$ 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 $\{\cal B\}$ u = f on [0,1]n with possibly large n. Under certain conditions on $\{\cal B\}$, the scheme is of essentially optimal and dimension independent complexity $\mathcal\{O\}$(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 $\{\cal B\}$ are not satisfied, the complexity can be bounded by $\mathcal\{O\}$(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 κ$(\cdot,\cdot)$ that can be singular on all secondary diagonals. Practical examples of such operators from Mathematical Finance are given and some numerical results are presented. },
author = {Reich, Nils},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
keywords = {Wavelet compression; sparse grids; anisotropic integrodifferential operators; norm equivalences; wavelet compression; convergence; partial integrodifferential equations; financial mathematics; complexity},
language = {eng},
month = {3},
number = {1},
pages = {33-73},
publisher = {EDP Sciences},
title = {Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces},
url = {http://eudml.org/doc/250788},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Reich, Nils
TI - Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces
JO - ESAIM: Mathematical Modelling and Numerical Analysis
DA - 2010/3//
PB - EDP Sciences
VL - 44
IS - 1
SP - 33
EP - 73
AB - For a class of anisotropic integrodifferential operators ${\cal B}$ 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 ${\cal B}$ u = f on [0,1]n with possibly large n. Under certain conditions on ${\cal B}$, the scheme is of essentially optimal and dimension independent complexity $\mathcal{O}$(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 ${\cal B}$ are not satisfied, the complexity can be bounded by $\mathcal{O}$(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 κ$(\cdot,\cdot)$ that can be singular on all secondary diagonals. Practical examples of such operators from Mathematical Finance are given and some numerical results are presented.
LA - eng
KW - Wavelet compression; sparse grids; anisotropic integrodifferential operators; norm equivalences; wavelet compression; convergence; partial integrodifferential equations; financial mathematics; complexity
UR - http://eudml.org/doc/250788
ER -

References

top
  1. Y. Achdou and O. Pironneau, A numerical procedure for calibration of volatility with American options. Appl. Math. Finance12 (2005) 201–241.  Zbl1138.91414
  2. Y. Achdou and N. Tchou, Variational analysis for the Black and Scholes equation with stochastic volatility. ESAIM: M2AN36 (2002) 373–395.  Zbl1137.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.  Zbl0983.60028
  4. J. Bertoin, Lévy processes. Cambridge University Press, Cambridge, UK (1996).  Zbl0861.60003
  5. G. Beylkin, R. Coifman and V. Rokhlin, The fast wavelet transform and numerical algorithms. Comm. Pure Appl. Math.44 (1991) 141–183.  Zbl0722.65022
  6. J.H. Bramble, A. Cohen and W. Dahmen, Multiscale problems and methods in numerical simulations, Lecture Notes in Mathematics1825. 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. Complexity15 (1999) 167–199.  Zbl0954.65078
  8. A. Cohen, I. Daubechies and J.-C. Feauveau, Biorthogonal bases of compactly supported wavelets. Comm. Pure Appl. Math.45 (1992) 485–560.  Zbl0776.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).  Zbl0980.65130
  10. A. Cohen, W. Dahmen and R. DeVore, Adaptive wavelet methods. II. Beyond the elliptic case. Found. Comput. Math.2 (2002) 203–245.  Zbl1025.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).  Zbl1052.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.  Zbl1101.47059
  13. W. Dahmen and R. Schneider, Wavelets with complementary boundary conditions – function spaces on the cube. Results Math.34 (1998) 255–293.  Zbl0931.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.  Zbl0826.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.  Zbl0847.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.  Zbl0922.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).  Zbl1113.65114
  18. F. Delbaen and W. Schachermayer, A general version of the fundamental theorem of asset pricing. Math. Ann.300 (1994) 463–520.  Zbl0865.90014
  19. F. Delbaen and W. Schachermayer, The variance-optimal martingale measure for continuous processes. Bernoulli2 (1996) 81–105.  Zbl0849.60042
  20. F. Delbaen, P. Grandits, T. Rheinländer, D. Samperi, M. Schweizer and C. Stricker, Exponential hedging and entropic penalties. Math. Finance12 (2002) 99–123.  Zbl1072.91019
  21. M. Demuth and J. van Casteren, Stochastic Spectral Theory for Selfadjoint Feller Operators. Birkhäuser Verlag, Basel (2000).  Zbl0980.60005
  22. R. DeVore, Nonlinear approximation, in Acta numerica (1998), Acta Numer.7, Cambridge Univ. Press, Cambridge, UK (1998) 51–150.  Zbl0931.65007
  23. A. Ern and J.-L. Guermond, Theory and practice of Finite Elements. Springer Verlag, New York, USA (2004).  Zbl1059.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.  Zbl1137.91446
  25. T. Gantumur and R. Stevenson, Computation of differential operators in wavelet coordinates. Math. Comp.75 (2006) 697–709 (electronic).  Zbl1158.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).  Zbl1115.41023
  27. M. Griebel and S. Knapek, Optimized general sparse grid approximation spaces for operator equations. Math. Comp. (to appear).  Zbl1198.65053
  28. M. Griebel, P. Oswald and T. Schiekofer, Sparse grids for boundary integral equations. Numer. Math.83 (1999) 279–312.  Zbl0935.65131
  29. H. Harbrecht and R. Schneider, Biorthogonal wavelet bases for the boundary element method. Math. Nachr.269/270 (2004) 167–188.  Zbl1055.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).  Zbl1117.65162
  31. N. Hilber, A.-M. Matache and C. Schwab, Sparse wavelet methods for option pricing under stochastic volatility. J. Comput. Finance8 (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).  Zbl1195.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).  Zbl0922.47045
  35. L. Hörmander, Linear partial differential operators, Grundlehren der Mathematischen Wissenschaften116 [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, Germany (1963).  
  36. L. Hörmander, The analysis of linear partial differential operators. III: Pseudodifferential operators, Grundlehren der Mathematischen Wissenschaften274 [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, Germany (1985).  
  37. N. Jacob, Pseudo Differential Operators and Markov Processes, Vol. 2: Generators and their potential theory. Imperial College Press, London, UK (2002).  Zbl1005.60004
  38. N. Jacob, Pseudo Differential Operators and Markov Processes, Vol. 3: Markov processes and applications. Imperial College Press, London, UK (2005).  Zbl1076.60003
  39. S. Knapek and F. Koster, Integral operators on sparse grids. SIAM J. Numer. Anal.39 (2001/2002) 1794–1809 (electronic).  Zbl1011.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: M2AN38 (2004) 37–71.  Zbl1072.60052
  42. A.-M. Matache, P.A. Nitsche and C. Schwab, Wavelet Galerkin pricing of American contracts on Lévy driven assets. Quant. Finance5 (2005) 403–424.  Zbl1134.91450
  43. H. Nguyen and R. Stevenson, Finite element wavelets on manifolds. IMA J. Numer. Math.23 (2003) 149–173.  Zbl1016.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.  Zbl1154.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 .  URIhttp://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. Theory63 (2009) 127–150.  Zbl1177.60069
  49. N. Reich, C. Schwab and C. Winter, On Kolmogorov equations for anisotropic multivariate Lévy processes. Finance Stoch. (to appear).  Zbl1226.91092
  50. K.-I. Sato, Lévy Processes and Infinitely Divisible Distributions. Cambridge University Press, Cambridge, UK (1999).  Zbl0973.60001
  51. R. Schneider, Multiskalen- und Wavelet-Matrixkompression: Analysisbasierte Methoden zur Lösung großer vollbesetzter Gleichungssysteme. B.G. Teubner, Stuttgart, Germany (1998).  
  52. C. Schwab and R. Stevenson, Adaptive wavelet algorithms for elliptic PDE's on product domains. Math. Comp.77 (2008) 71–92 (electronic).  Zbl1127.41009
  53. R.E. Showalter, Monotone Operators in Banach Space and Nonliner Partial Differential Equations. American Mathematical Society, Rhode Island, USA (1997).  Zbl0870.35004
  54. E.M. Stein, Harmonic Analysis. Princeton University Press, Princeton, USA (1993).  
  55. R. Stevenson, On the compressibility of operators in wavelet coordinates. SIAM J. Math. Anal.35 (2004) 1110–1132 (electronic).  Zbl1087.47012
  56. M.E. Taylor, Pseudodifferential operators. Princeton University Press, Princeton, USA (1981).  Zbl0453.47026
  57. H. Triebel, Interpolation theory, function spaces, differential operators. Second edition, Johann Ambrosius Barth Verlag, Heidelberg, Germany (1995).  
  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).  Zbl1050.65134
  60. T. von Petersdorff and C. Schwab, Numerical solution of parabolic equations in high dimensions. ESAIM: M2AN38 (2004) 93–127.  Zbl1083.65095
  61. T. von Petersdorff, C. Schwab and R. Schneider, Multiwavelets for second-kind integral equations. SIAM J. Numer. Anal.34 (1997) 2212–2227.  Zbl0891.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 .  URIhttp://e-collection.ethbib.ethz.ch/view/eth:41555

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.