A fourth order finite difference method for solving elliptic interface problems with the FFT acceleration

In this paper, a new Cartesian grid finite difference method is introduced based on the fourth order accurate matched interface and boundary (MIB) method and fast Fourier transform (FFT). The proposed augmented MIB method consists of two major parts for solving elliptic interface problems in two dimensions. For the interior part, in treating a smoothly curved interface, zeroth and first order jump conditions are enforced repeatedly by the MIB scheme to generate fictitious values near the interface. For the exterior part, two layers of zero-padding solutions are introduced beyond the original rectangular domain so that the FFT inversion becomes feasible. Different types of boundary conditions, including Dirichlet, Neumann, Robin and their mix combinations, can be imposed via the MIB scheme to generate fictitious values near boundaries. Based on fictitious values at both interfaces and boundaries, the augmented MIB method reconstructs Cartesian derivative jumps as auxiliary variables. Then, by treating such variables as unknowns, an enlarged linear system is obtained. In the Schur complement solution of such system, the FFT algorithm will not sense the solution discontinuities, so that the discrete Laplacian can be efficiently inverted. Therefore, the FFT-based augmented MIB not only achieves a fourth order of accuracy in dealing with interfaces and boundaries, but also produces an overall complexity of O ( n 2 log ⁡ n ) for a n × n uniform grid. Moreover, the augmented MIB scheme can provide fourth order accurate approximations to solution gradients and fluxes.