Wavelet Methods - Computational Methods for Quantitative Finance - page 159

Chapter 12
Wavelet Methods

In the previous sections, we developed various algorithms for the efficient pricing of
derivative contracts when the price of the underlying is a one-dimensional diffusion,
a multidimensional diffusion, a general stochastic volatility or a one-dimensional
Lévy process. In this part, we introduce variational numerical methods for pricing
under yet more general processes with the aim of achieving linear complexity .
We say an asset pricing algorithm has linear complexity if it yields, for one payoff
function, a vector of N option prices at maturity T> 0 in essentially, i.e. up to pow-
ers of log N ,

O (N) memory. It is of order s> 0,
if the error in the computed option prices decreases asymptotically, as N

O (N) operations and in essentially

→∞ , and

(N − s ) .
Consider, for example, the valuation of a European plain vanilla contract under
either a local volatility or under constant elasticity of variance (see Sect. 4.5)as-
sumptions. We use piecewise linear finite elements on a mesh of width h> 0in
log-price space and the θ -scheme in time with time step k

is O

= O (h) . The number

(h − 1 ) . There of degrees of freedom equals the number of grid points, i.e. N = O

(k − 1 ) are T and in each time step,

a linear system of equations with a tridiagonal matrix must be solved. Direct solu-
tion of a tridiagonal, linear system with a diagonally dominant coefficient matrix
requires

O = O (N) number of time steps to reach t =

(N) operations. Hence continuous, piecewise linear finite element meth-
ods in space and implicit time-stepping are of complexity

O

(N 2 ) and of accuracy at

O

O (h 2 ) = O (N − 2 ) . 1 For a European plain vanilla contract in a Lévy market (see
Sect. 10.6), we obtain an overall complexity of

best

(N 3 ) operations since the matrix
to be inverted in each time step is fully populated and of size N .
These examples show that we only have superlinear complexity. Our goal in this
chapter is to develop deterministic pricing algorithms of linear complexity. This is
achieved by the following ingredients:
(i) High order, discontinuous Galerkin time stepping from t =

O

0to T , to exploit

analyticity of the transition semigroup of the price process,

1 High order timestepping [146, 147] and the so-called hp -Finite Element Methods can improve on
this substantially, at the expense of more involved implementations.