A fast multipole accelerated method of fundamental solutions for potential problems

The fast multipole method (FMM) is a very effective way to accelerate the numerical solutions of the methods based on Green's functions or fundamental solutions. Combined with the FMM, the boundary element method (BEM) can now solve large-scale problems with several million unknowns on a desktop computer. The method of fundamental solutions (MFS), also called superposition or source method and based on the fundamental solutions but without using integrals, has been studied for several decades along with the BEM. The MFS is a boundary meshless method in nature and offers more flexibility in modeling of a problem. It also avoids the singularity of the kernel by placing the source at some auxiliary points off the problem domain. However, like the traditional BEM, the conventional MFS also requires O(N2) operations to compute the system of equations and another O(N3) operations to solve the system using direct solvers, with N being the number of unknowns. Combining the FMM and MFS can potentially reduce the operations in formation and solution of the MFS system, as well as the memory requirement, all to O(N). This paper is an attempt in this direction. The FMM formulations for the MFS is presented for 2D potential problem. Issues in implementation of the FMM for the MFS are discussed. Numerical examples with up to 200,000 DOF's are solved successfully on a Pentium IV PC using the developed FMM MFS code. These results clearly demonstrate the efficiency, accuracy and potentials of the fast multipole accelerated MFS.