In this talk, we will discuss multigrid methods for solving time-dependent 2D partial differential equations (PDEs) arising in option pricing theory. The problem considered is the computation of the value of an option of American-style in a stochastic volatility setting. It leads to the solution of a convection-diffusion type PDE with a free, beforehand unknown boundary. In [4], it has been shown that for American-style options the theory of linear complementarity, as it is developed in the 1970-ties applies. It is possible to rewrite the arising free boundary problems to linear complementarity problems (LCPs), of the form
plus boundary conditions, where L is a differential operator.
This formulation is beneficial for iterative solution, since the unknown boundary does not appear explicitly and can be obtained in a postprocessing step.
A slight disadvantage of this formulation is that the linear partial differential equation has been transformed into a nonlinear partial differential inequality.
In 1983, Brandt and Cryer [1] proposed a multigrid method for LCPs arising from free boundary problems. The algorithm is a multigrid generalization of the projected SOR method. Due to the nonlinear character of the problem, the multigrid method is based on the full approximation scheme, FAS. The solution method has therefore been called the projected full approximation scheme, PFAS in [1]. In the original paper, the operator L in (1,3) was the nicely elliptic Laplace operator and fast convergence was presented. PFAS has been successfully used in the financial community for American options with stochastic volatility in [2]. The smoother applied in [2] is, however, somewhat involved. It is based on the pointwise PSOR method for the detection of the free boundary, followed by a linewise version in order to deal with the stretched numerical grid occurring in the financial problem. The need to change multigrid components like the smoother for optimal convergence of a new problem at hand is sometimes considered as unsatisfactory.
It is our aim to give some more insight in the multigrid convergence for the problems from option pricing. At the same time, we will introduce some recent developments in multigrid techniques to the field of LCPs, making the algorithms more robust, i.e. less sensitive to parameter changes.
In the search for efficient solvers that are more generally applicable, we consider multigrid as a preconditioner for Krylov subspace methods. Often different complications such as anisotropies, nonlinearities or strong positive off-diagonal stencil elements occur simultaneously, as is the case in the discretization of the PDEs arising from American-style option pricing, for example discretized by a higher-order upwind scheme.
The fundamental idea of multigrid, to reduce the high frequency components of the error by smoothing procedures and to take care of the low frequency error components by coarse grid corrections, might not work optimally if straightforward multigrid approaches are used. Certain error components may remain large since they cannot be reduced by pointwise Gauss-Seidel-type smoothing procedures combined with a standard coarse grid approximation. These specific error components (and the corresponding eigenvectors/eigenvalues) are then responsible for the poor multigrid convergence.
A commonly known solution approach for nonlinear equations is to apply global (Newton) linearization, solve the arising linear system with a Krylov subspace method, like GMRES or BiCGSTAB and a multigrid preconditioner. This is not the approach followed here. We apply to nonlinear problems a solution method based on PFAS as the multigrid technique. The Krylov subspace acceleration can be interpreted as a technique, in which intermediate iterants are recombined in order to obtain an improved approximation, see, for example [3]. We will generalize this method to solving LCPs.