n this section we put into use the
recipes developed in the section
(
Implementation tools II
).
Our goal is to show that we can conduct high-precision finite element
calculations for elliptic and parabolic PDEs on small grids. The possibility
of small grid representation changes motivations behind finite element
calculations and introduces effective techniques that are prohibited
otherwise. Notably, we remove stiffness that is typically present in financial
problems.
The research covers problems with stochastic optimization features.
The goal is accomplished by using high order multiscaled wavelet bases,
adaptive selection of such bases and application of preconditioners.
High-order wavelet bases pack information. Each function has lengthy
piecewise-polynomial representation. We store it once and reuse it for
multiple dimensions and problems.
Multiscale feature facilitates construction of adaptive grids. We start from a
set of scaling functions and then we add wavelets of various scales and
locations to improve precision.
Adaptive selection of bases further packs information by placing wavelets
where these count most.
Preconditioning removes numerical stability issues and accelerates
calculations.
Using high order wavelets and multiscaled structure brings new difficulties as
well as advantages. After discretization we arrive to a non-sparse matrix. For
one or two dimensions this is not a problem. For example, we solve Black
equation without log-change (leaving
term in place) using wavelet basis consisting of 50 functions with practical
precision. We also solve mean-reverting equation (with
term) using a basis of 24 functions. With use of parametrix technique this
number can get even lower. However, for higher dimensions this is a problem
and the technique for resolution of this difficulty is suggested in the
section (
Solving N-dimensional
PDEs
).
The second difficulty is lengthy representation of wavelet basis
.
Each function is a piecewise polynomial with 100-200 pieces for one dimension,
depending on particulars of the problem. We counter this difficulty by
precalculating bases, precalculating Gram matrixes and scalar products such as
or
.
We also use scaling relationships, such as
(
Scaling equation
) and
(
Dual wavelets
). However, in some industrial
situations a client might require a solution with minimal infrastructure. In
such case one can drop down to Haar functions, see section
(
Haar functions
). Then calculation of
scalar products becomes easy, matrixes become sparse but the size of every
dynamic piece of data becomes large. The recipes are the same with minor
corrections.
The third difficulty is impossibility of backward induction in multiple
dimensions. High order scaling functions and wavelets have large overlapping
supports. Wavelets of any order have variable sign. In such situation taking
straight pointwise maximum of basis decompositions is meaningless.
Reassembling basis decompositions is prohibited in multiple dimensions because
we would arrive to a representation on a fine grid without adaptive selection
or sparsity. Thus, taking max by definition is not possible. Some researchers
suggest variational inequalities as a cure. The author of this text found that
variational inequalities lead to extremely stiff numerical techniques. This
matter is discussed and experimented in the section
(
Stochastic
optimization over wavelet basis
). In the same section we suggest a
technique which is a hybrid of backward induction and penalty function
approaches that leads to satisfactory results, see sections
(
Mix
of backward induction and penalty term approaches II
) and
(
How does it
extend to multiple dimensions
).
The codes in this section are written in Python and accelerated by using
C++/Cuda extension libraries. We test technologies and recipes and provide
baseline for further development.
We assume that the modules r_com, poly and PiecewisePoly are already
installed. See the sections
(
Python to R Communicator
),
(
Piecewise polynomials
) and
(
Manipulation
of localized piecewise polynomial functions
).
Presentation of this section is a journal of incomplete research.
|