Quantitative Analysis
Parallel Processing
Numerical Analysis
C++ Multithreading
Python for Excel
Python Utilities
Services
Author

I. Wavelet calculations.
II. Calculation of approximation spaces in one dimension.
III. Calculation of approximation spaces in one dimension II.
IV. One dimensional problems.
V. Stochastic optimization in one dimension.
VI. Scalar product in N-dimensions.
VII. Wavelet transform of payoff function in N-dimensions.
VIII. Solving N-dimensional PDEs.

Numerical Analysis.


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 $x^{2}$ term in place) using wavelet basis consisting of 50 functions with practical precision. We also solve mean-reverting equation (with $x^{2}$ 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 MATH . 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 MATH or MATH . 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.



Table of Contents.

I. Wavelet calculations.
1. Calculation of scaling filters.
2. Calculation of scaling functions.
3. Calculation of wavelets.
4. Convergence of cascade procedure.
5. Direct verification of wavelet properties.
6. Adapting scaling function to the interval [0,1].
7. Adapting wavelets to the interval [0,1].
II. Calculation of approximation spaces in one dimension.
1. Calculation of boundary scaling functions.
2. Calculation of boundary wavelets.
3. Testing properties of boundary wavelets and scaling functions.
III. Calculation of approximation spaces in one dimension II.
1. Crudification of piecewise-quadratic representation.
2. Convergence of modified cascade procedure.
3. Calculation of boundary scaling functions II.
IV. One dimensional problems.
1. Decomposition of payoff function in one dimension. Adaptive multiscaled approximation.
2. Constructing wavelet basis with Dirichlet boundary conditions.
3. Accelerated calculation of Gram matrix.
4. Adapting wavelet basis to arbitrary interval.
5. Solving one dimensional elliptic PDEs.
6. Discontinuous Galerkin technique II.
A. Rebalancing wavelet basis.
B. Reduction to system of linear algebraic equations.
7. Solving one dimensional Black PDE.
A. Example Black equation parameters.
B. Reduction to system of linear algebraic equations for Black PDE.
C. Adaptive time step for Black PDE.
D. Localization.
E. Reduction to system of linear algebraic equations for q=1.
F. Preconditioner for Black equation in case q=1.
a. Analytical preconditioner derived from asymptotic decomposition in time.
b. Diagonal preconditioner.
c. Symmetrization and symmetric preconditioning.
d. Reduction to well conditioned form.
e. Analytical preconditioner derived from inversion of Black equation.
G. Summary for Black equation in case q=1.
H. Implementation of Black equation solution.
8. Solving one dimensional mean reverting equation.
A. Reduction to system of linear algebraic equations for mean reverting equation.
B. Evaluating matrix R.
C. Localization for mean reverting equation.
D. Implementation for mean reverting equation.
V. Stochastic optimization in one dimension.
1. Review of variational inequalities in maximization case.
2. Penalized problem for mean reverting equation.
3. Impossibility of backward induction.
4. Stochastic optimization over wavelet basis.
A. Choosing probing functions.
B. Time discretization of penalty term.
C. Implicit formulation of penalty term.
D. Smooth version of penalty term.
E. Solving equation with implicit penalty term.
F. Removing stiffness from penalized equation.
G. Mix of backward induction and penalty term approaches I.
H. Mix of backward induction and penalty term approaches I. Implementation and results.
I. Mix of backward induction and penalty term approaches II.
J. Mix of backward induction and penalty term approaches II. Implementation and results.
K. Review. How does it extend to multiple dimensions?
VI. Scalar product in N-dimensions.
1. Two-sided area of integration, positive a.
A. Calculation of w1 for positive a.
B. Calculation of w2 for positive a.
C. Calculation of w3 for positive a.
2. Two-sided area of integration, negative a.
A. Calculation of w1 for negative a.
B. Calculation of w2 for negative a.
C. Calculation of w3 for negative a.
3. Indexing integration domains.
4. Summary. Calculation of scalar product in N dimensions.
5. Indexing integration domains II.
6. Scalar product in N-dimensions. Test case 1.
7. Scalar product in N-dimensions. Test case 2.
8. Scalar product in N-dimensions. Test case 3.
9. Implementation of scalar product in N-dimensions.
VII. Wavelet transform of payoff function in N-dimensions.
1. Separation of variables for payoff function.
VIII. Solving N-dimensional PDEs.



















Copyright 2007