Hows, Whys and Wherefores of FEM in Quantitative Finance - III

Grid Generation
In contrast to physics and engineering, where the optimal element type and approximation order is often determined by the nature of the problem, the situation is not equally clear when applying the finite element method to financial problems. Two key questions need to be asked in advance of tackling a problem:

(1) Is it necessary to dynamically adapt the mesh during the simulation process (for example by locally adding additional elements to refine the mesh)?

(2) Are derivatives of the (approximate) solution required with high order?

To answer the first question we look at the problems's spatial dimension. A simple Hull & White Model leading to a 1+1 (spatial and time dimension) dimensional partial differential equation (PDE) can be solved fast without the need of applying refinement techniques. This picture changes when for example a corss currency swap needs to be valuated. Using two one factor short rate models (for example two Hull & White models) and a one factor model (Garman and Kohlhagen) for the FX rate one will end with a 3+1 dimensional PDE. In this case a clever mesh refinement strategy can boost your calculation.
The answer to the second question indicates the required order of approximation: If the calculation of greeks or similar quantities connected with derivatives in higher order is of relevance, higher order approximations should be used.

Although for technical applications, the mesh generation algorithms employed, generally involve complex iterative smoothing techniques that attempt to align elements with boundaries or physical domains, in the field of financial engineering structured rectangular or hexahedral meshes can be easily generated using tensor products (cartesian grids) leading to structured meshes. Strictly speaking, a structured mesh, like the one in the figure below, can be identified by all interior nodes of the mesh having an equal number of adjacent elements. These meshes may also serve as starting points for structured triangular or tetrahedral meshes.

Structured Mesh

Unstructured meshes, on the other hand, drop the node valence requirement and allow any number of elements to meet at a single node. Triangular and tetrahedral meshes are by far the most common forms used here.

Unstructured mesh. Additionally local grid refinement is applied. 

Most mesh generation techniques for unstructured meshes currently in use fall into one of three categories, namely the Quad/Octree technique, Delauny triangulation and the advancing front algorithm.

The Octree technique recursively subdivides cubes or quads containing the computational domain until the desired resolution is achieved. Today methods based on Delauny criterion are by far the most popular methods among the triangular and tetrahedral meshing techniques. Put simply, the Delaunay criterion states that any node must not be contained inside the circumsphere/circumcircle of any tetrahedra/- triangle within the mesh. Another popular family of triangular and tetrahedral mesh generation algorithms is the advancing (or moving) front method. Tetrahedra are progressively built from the triangulated surface of the computational domain inward. An active front is maintained where new tetrahedra/triangles are formed.
To obtain unstructured quadrilateral or hexahedral meshes, unstructured triangular or tetrahedral meshes often serve as starting points. 
This series of blog posts summarizes a chapter of the book A Workout in Computational Finance

The fourth post of the series will be published on Thursday, June 20 and will give an overview over different element types.