Efficient d-multigrid preconditioners for sparse-grid solution of high-dimensional partial differential equations

Abstract

Fast and efficient solution techniques are developed for high-dimensional parabolic partial differential equations (PDEs). In this paper we present a robust solver based on the Krylov subspace method Bi-CGSTAB combined with a powerful, and efficient, multigrid preconditioner. Instead of developing the perfect multigrid method, as a stand-alone solver for a single problem discretized on a certain grid, we aim for a method that converges well for a wide class of discrete problems arising from discretization on various anisotropic grids. This is exactly what we encounter during a sparse grid computation of a high-dimensional problem. Different multigrid components are discussed and presented with operator construction formulae. An option-pricing application is focused and presented with results computed with this method.

Keywords:

• Anisotropic diffusion equation
• Coarsening strategies
• High-dimensional PDE
• Sparse grids
• Multigrid preconditioned Bi-CGSTAB

Acknowledgements

This research has been partially supported by the Dutch government through the national program BSIK: knowledge and research capacity, in the ICT project BRICKS (http://www.bsik-bricks.nl), theme MSV1, partially by the Government of Pakistan through The HEC-Pakistan research grant, contract Ref: 1-3/PM-OVER/Neth/SPMU/2004 and partially by the Dutch Technology foundation STW. We would like to express our thanks to these sponsors.