Option pricing with a direct adaptive sparse grid approach

We present an adaptive sparse grid algorithm for the solution of the Black–Scholes equation for option pricing, using the finite element method. Sparse grids enable us to deal with higher-dimensional problems better than full grids. In contrast to common approaches that are based on the combination technique, which combines different solutions on anisotropic coarse full grids, the direct sparse grid approach allows for local adaptive refinement. When dealing with non-smooth payoff functions, this reduces the computational effort significantly. In this paper, we introduce the spatially adaptive discretization of the Black–Scholes equation with sparse grids and describe the algorithmic structure of the numerical solver. We present several strategies for adaptive refinement, evaluate them for different dimensionalities, and demonstrate their performance showing numerical results.     

Adaptive sparse grid algorithms with applications to electromagnetic scattering under uncertainty

We discuss adaptive sparse grid algorithms for stochastic differential equations with a particular focus on applications to electromagnetic scattering by structures with holes of uncertain size, location, and quantity. Stochastic collocation (SC) methods are used in combination with an adaptive sparse grid approach based on nested Gauss-Patterson grids. As an error estimator we demonstrate how the nested structure allows an effective error estimation through Richardson extrapolation. This is shown to allow excellent error estimation and it also provides an efficient means by which to estimate the solution at the next level of the refinement. We introduce an adaptive approach for the computation of problems with discrete random variables and demonstrate its efficiency for scattering problems with a random number of holes. The results are compared with results based on Monte Carlo methods and with Stroud based integration, confirming the accuracy and efficiency of the proposed techniques.     

An interior point algorithm with inexact step computation in function space for state constrained optimal control

We consider an interior point method in function space for PDE constrained optimal control problems with state constraints. Our emphasis is on the construction and analysis of an algorithm that integrates a Newton path-following method with adaptive grid refinement. This is done in the framework of inexact Newton methods in function space, where the discretization error of each Newton step is controlled by adaptive grid refinement in the innermost loop. This allows to perform most of the required Newton steps on coarse grids, such that the overall computational time is dominated by the last few steps. For this purpose we propose an a-posteriori error estimator for a problem suited norm.     

An a posteriori error estimator for anisotropic refinement

Summary. Besides an algorithm for local refinement, an a posteriori error estimator is the basic tool of every adaptive finite element method. Using information generated by such an error estimator the refinement of the grid is controlled. For 2nd order elliptic problems we present an error estimator for anisotropically refined grids, like -d cuboidal and 3-d prismatic grids, that gives correct information about the size of the error; additionally it generates information about the direction into which some element has to be refined to reduce the error in a proper way. Numerical examples are presented for 2-d rectangular and 3-d prismatic grids. Received March 15, 1994 / Revised version received June 3, 1994     

Adaptive p-version of the finite element method for solving boundary value problems for ordinary second-order differential equations

We suggest an adaptive strategy for constructing a hierarchical basis for a p-version of the finite element method used to solve boundary value problems for second-order ordinary differential equations. The choice of the order of an element on each grid interval is based on estimates of the change, in the norm of C, of the approximate solution or the value of the functional to be minimized when increasing the degree of the basis function added on this interval. The results of numerical experiments estimating the method efficiency are given for sample problems whose solutions have singularities of the boundary layer type. We make a comparison with the p-version of the finite element method, which uses a uniform growth of the degree of the basis functions, and with the h-version, which uses uniform grid refinement along with an adaptive grid refinement and coarsening strategy.     

Preconditioned conjugate gradient methods for large-scale fluid flow applications

The simulation of large-scale fluid flow applications often requires the efficient solution of extremely large nonsymmetric linear and nonlinear sparse systems of equations arising from the discretization of systems of partial differential equations. While preconditioned conjugate gradient methods work well for symmetric, positive-definite matrices, other methods are necessary to treat large, nonsymmetric matrices. The applications may also involve highly localized phenomena which can be addressed via local and adaptive grid refinement techniques. These local refinement methods usually cause non-standard grid connections which destroy the bandedness of the matrices and the associated ease of solution and vectorization of the algorithms. The use of preconditioned conjugate gradient or conjugate-gradient-like iterative methods in large-scale reservoir simulation applications is briefly surveyed. Then, some block preconditioning methods for adaptive grid refinement via domain decomposition techniques are presented and compared. These techniques are being used efficiently in existing large-scale simulation codes.     

A multigrid preconditioner for an adaptive Black-Scholes solver

This paper is concerned with the efficient solution of the linear systems of equations that arise from an adaptive space-implicit time discretisation of the Black-Scholes equation. These nonsymmetric systems are very large and sparse, so an iterative method will usually be the method of choice. However, such a method may require a large number of iterations to converge, particularly when the timestep used is large (which is often the case towards the end of a simulation which uses adaptive timestepping). An appropriate preconditioner is therefore desirable. In this paper we show that a very simple multigrid algorithm with standard components works well as a preconditioner for these problems. We analyse the eigenvalue spectrum of the multigrid iteration matrix for uniform grid problems and illustrate the method’s efficiency in practice by considering the results of numerical experiments on both uniform grids and those which use adaptivity in space.     

Conjugate Grids for Unconstrained Optimisation

Several recent papers have proposed the use of grids for solving unconstrained optimisation problems. Grid-based methods typically generate a sequence of grid local minimisers which converges to stationary points under mild conditions.In this paper the location and number of grid local minimisers is calculated for strictly convex quadratic functions in two dimensions with certain types of grids. These calculations show it is possible to construct a grid with an arbitrary number of grid local minimisers. The furthest of these can be an arbitrary distance from the quadratic's minimiser. These results have important implications for the design of practical grid-based algorithms.Grids based on conjugate directions do not suffer from these problems. For such grids only the grid points closest (depending on the choice of metric) to the minimiser are grid local minimisers. Furthermore, conjugate grids are shown to be reasonably stable under mild perturbations so that in practice, only approximately conjugate grids are required.     

Front tracking for two-phase flow in reservoir simulation by adaptive mesh

In this article, an algorithm for the numerical approximation of two-phase flow in porous media by adaptive mesh is presented. A convergent and conservative finite volume scheme for an elliptic equation is proposed, together with the finite difference schemes, upwind and MUSCL, for a hyperbolic equation on grids with local refinement. Hence, an IMPES method is applied in an adaptive composite grid to track the front of a moving solution. An object-oriented programmation technique is used. The computational results for different examples illustrate the efficiency of the proposed algorithm. © 1997 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 13: 673–697, 1997     

Selected Recent Applications of Sparse Grids

Sparse grids have become a versatile tool for a vast range of applications reaching from interpolation and numerical quadrature to data-driven problems and uncertainty quantification. We review four selected real-world applications of sparse grids: financial product pricing with the Black-Scholes model, interactive exploration of simulation data with sparse-grid-based surrogate models, analysis of simulation data through sparse grid data mining methods, and stability investigations of plasma turbulence simulations.     

Design of Finite Element Tools for Coupled Surface and Volume Meshes

Many problems with underlying variational structure involve a coupling of volume with surface effects.A straight-forward approach in a finite element discretiza- tion is to make use of the surface triangulation that is naturally induced by the volume triangulation.In an adaptive method one wants to facilitate"matching"local mesh modifications,i.e.,local refinement and/or coarsening,of volume and surface mesh with standard tools such that the surface grid is always induced by the volume grid. We describe the concepts behind this approach for bisectional refinement and describe new tools incorporated in the finite element toolbox ALBERTA.We also present several important applications of the mesh coupling.     

Asymptotics of generalized derangements

An adaptive wavelet-based method is proposed for solving TV(total variation)–Allen–Cahn type models for multi-phase image segmentation. The adaptive algorithm integrates (i) grid adaptation based on a threshold of the sparse wavelet representation of the locally-structured solution; and (ii) effective finite difference on irregular stencils. The compactly supported interpolating-type wavelets enjoy very fast wavelet transforms, and act as a piecewise constant function filter. These lead to fairly sparse computational grids, and relax the stiffness of the nonlinear PDEs. Equipped with this algorithm, the proposed sharp interface model becomes very effective for multi-phase image segmentation. This method is also applied to image restoration and similar advantages are observed.     

Grid structure impact in sparse point representation of derivatives

In the Sparse Point Representation (SPR) method the principle is to retain the function data indicated by significant interpolatory wavelet coefficients, which are defined as interpolation errors by means of an interpolating subdivision scheme. Typically, a SPR grid is coarse in smooth regions, and refined close to irregularities. Furthermore, the computation of partial derivatives of a function from the information of its SPR content is performed in two steps. The first one is a refinement procedure to extend the SPR by the inclusion of new interpolated point values in a security zone. Then, for points in the refined grid, such derivatives are approximated by uniform finite differences, using a step size proportional to each point local scale. If required neighboring stencils are not present in the grid, the corresponding missing point values are approximated from coarser scales using the interpolating subdivision scheme. Using the cubic interpolation subdivision scheme, we demonstrate that such adaptive finite differences can be formulated in terms of a collocation scheme based on the wavelet expansion associated to the SPR. For this purpose, we prove some results concerning the local behavior of such wavelet reconstruction operators, which stand for SPR grids having appropriate structures. This statement implies that the adaptive finite difference scheme and the one using the step size of the finest level produce the same result at SPR grid points. Consequently, in addition to the refinement strategy, our analysis indicates that some care must be taken concerning the grid structure, in order to keep the truncation error under a certain accuracy limit. Illustrating results are presented for 2D Maxwell’s equation numerical solutions.     

Application of the spherical metric tensor to grid adaptation and the solution of applied problems

New results concerning the construction and application of adaptive numerical grids for solving applied problems are presented. The grid generation technique is based on the numerical solution of inverted Beltrami and diffusion equations for a monitor metric. The capabilities of the spherical metric tensor as applied to adaptive grid generation are examined in detail. Adaptive hexahedral grids are used to numerically solve a boundary value problem for the three-dimensional heat equation with a moving boundary in a continuous medium with discontinuous thermophysical parameters; this problem models the interaction of a thermal wave with a thermocouple embedded in the solid.     

Patch-adaptive multilevel iteration

Themultilevel adaptive iteration is an attempt to improve both the robustness and efficiency of iterative sparse system solvers. Unlike in most other iterative methods, the order of processing and sequence of operations is not determined a priori. The method consists of a relaxation scheme with an active set strategy and can be viewed as an efficient implementation of the Gauß-Southwell relaxation. With this strategy, computational work is focused on where it can efficiently improve the solution quality. To obtain full efficiency, the algorithm must be used on a multilevel structure. This algorithm is then closely related to multigrid or multilevel preconditioning algorithms, and can be shown to have asymptotically optimal convergence. In this paper the focus is on a variant that uses data structures with a locally uniform grid refinement. The resulting grid system consists of a collection of patches where each patch is a uniform rectangular grid and where adaptive refinement is accomplished by arranging the patches flexibly in space. This construction permits improved implementations that better exploit high performance computer designs. This will be demonstrated by numerical examples.     

A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.     

The Finite Difference Based Fast Adaptive Composite Grid Method

The fast adaptive composite grid (FAC) method is an iterative method for solving discrete boundary value problems on composite grids. McCormick introduced the method in [8] and considered the convergence behaviour for discrete problems resulting from finite volume element discretization on composite grids. In this paper we consider discrete problems resulting from finite difference discretization on composite grids. We distinguish between two obvious discretization approaches at the grid points on the interfaces between fine and coarse subgrids. The FAC method for solving such discrete problems is described. In the FAC method several intergrid transfer operators appear. We study how the convergence behaviour depends on these intergrid transfer operators. Based on theoretical insights, (quasi-)optimal intergrid transfer operators are derived. Numerical results illustrate the fast convergence of the FAC method using these intergrid transfer operators.     

Least‐squares finite element method on adaptive grid for PDEs with shocks

We apply the least‐squares finite element method with adaptive grid to nonlinear time‐dependent PDEs with shocks. The least‐squares finite element method is also used in applying the deformation method to generate the adaptive moving grids. The effectiveness of this method is demonstrated by solving a Burgers' equation with shocks. Computational results on uniform grids and adaptive grids are compared for the purpose of evaluation. The results show that the adaptive grids can capture the shock more sharply with significantly less computational time. For moving shock, the adaptive grid moves correctly with the shock. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

A comparative analysis of adaptive algorithms in the finite element method for solving the boundary value problem for a stationary reaction-diffusion equation

A new adaptive algorithm is proposed for constructing grids in the hp-version of the finite element method with piecewise polynomial basis functions. This algorithm allows us to find a solution (with local singularities) to the boundary value problem for a one-dimensional reaction-diffusion equation and smooth the grid solution via the adaptive elimination and addition of grid nodes. This algorithm is compared to one proposed earlier that adaptively refines the grid and deletes nodes with the help of an estimate for the local effect of trial addition of new basis functions and the removal of old ones. Results are presented from numerical experiments aimed at assessing the performance of the proposed algorithm on a singularly perturbed model problem with a smooth solution.     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.