Department of Information Technology

Radial basis function methods for high-dimensional PDE problems

Even with the most powerful computers of today, it is difficult and sometimes impossible to perform computer simulations of high-dimensional problems. The main reason is that the problem size grows exponentially with the number of dimensions and computer memory becomes a limitation. However, simulation time is also important in the sense that we need the answer while it is still interesting.

High-dimensional application problems can be found in e.g. financial mathematics, where the price of an option based on d underlying stocks can be computed through solving the d-dimensional Black-Scholes equation. Another example, from molecular biology, is the chemical balance in a cell. There, the dimensions are the different substances that interact and influence the system. Also in quantum dynamics, problems are very high dimensional. The number of dimensions in a system is proportional to the number of particles within a molecule.

The aim of this project is to develop simulation methods based on radial basis function (RBF) techniques that can handle high-dimensional problems. The range that we hope to be able to address is up to 5-6 dimensions to start with. The research is carried out in collaboration with researchers in the Numerical Finance and the Numerical Quantum Dynamics groups.

Financial Mathematics

Pricing of financial derivatives such as options can (in the simplest case) be described by the Black-Scholes equation. The equation becomes multi-dimensional when the options are based on several underlying assets. Typical numerical issues apart from the high-dimensionality are dealing with the discontinuous derivatives in the pay-off function which constitutes the final (initial) condition and boundary conditions.

Contributions

In the first paper, we look at how to choose boundary conditions when applying RBFs to Black-Scholes problems. We show numerically that spectral convergence in space can be achieved with a constant shape parameter. We reduce the computational cost by choosing a domain that is not a hypercube and by placing more nodes in the interesting region.

The second paper examines how symmetry can be exploited to reduce the computational cost. The Black-Scholes equation is transformed into the heat equation, the boundary conditions are treated as corrections and the symmetric part of the system matrix is transformed into block-diagonal form by using the generalized (based on group theory) Fourier transform.

  1. Multi-dimensional option pricing using radial basis functions and the generalized Fourier transform. Elisabeth Larsson, Krister Åhlander, and Andreas Hall. In Journal of Computational and Applied Mathematics, volume 222, pp 175-192, 2008. (DOI).
  2. Improved radial basis function methods for multi-dimensional option pricing. Ulrika Pettersson, Elisabeth Larsson, Gunnar Marcusson, and Jonas Persson. In Journal of Computational and Applied Mathematics, volume 222, pp 82-93, 2008. (DOI).

Multi2.jpg
The image of the transformed domain and node points

Ongoing projects

With Sônia Gomes: A least-squares multi-level RBF method.

Quantum Dynamics

The dynamics of a chemical reaction is governed by the time dependent Schrödinger equation (TDSE). The main challenges when numerically solving the TDSE are the curse of dimensionality and the fact that the problems are posed on an unbounded domain.

Since solutions to the TDSE are usually very smooth, high-order methods are convenient for this type of problems. It is very popular among quantum chemists to use the Fourier-based pseudospectral method for spatial discretization. Changing the basis to radial basis functions (RBF) has two potential advantages: Firstly, one is more flexible in selecting boundary conditions. In this way, it is possible to solve open boundary problems. Moreover, RBF allow for scattered node distributions, a means of adapting the point distribution to the shape of the solution instead of resolving the whole high-dimensional space.

In this project, we analyze radial basis function approximations for the problems studied by the Numerical Quantum Dynamics project group. Aspects that we are currently interested in include stability of the RBF discretization, Galerkin formulation, parameter choice for the basis function, transfer between basis sets, and conservation properties of the scheme.

qddoublewell.jpg

The figure shows the solution of the TDSE for a double well potential which includes tunneling effects.

Updated  2017-02-05 16:39:42 by Kurt Otto.