A RIGOROUS COMPARISON OF THE EWALD METHOD AND THE FAST MULTIPOLE METHOD IN 2 DIMENSIONS

The most efficient and proper standard method for simulating charged o r dipolar systems is the Ewald method, which asymptotically scales as N-3/2 where N is the number of charges. However, recently the ''fast m ultipole method'' (FMM) which scales linearly with N has been develope d. The break-even of the two methods (that is, the value of N below wh ich Ewald is faster and above which FMM is faster) is very sensitive t o the way the methods are optimized and implemented and to the require d simulation accuracy. In this paper we use theoretical estimates and simulation results for the accuracies to carefully compare the two met hods with respect to speed. We have developed and implemented highly e fficient algorithms for both methods for a serial computer (a SPARCsta tion ELC) as well as a parallel computer (a T800 transputer based MEIK O computer). Breakevens in the range between N = 10000 and N = 30000 w ere found for reasonable values of the average accuracies found in our simulations. Furthermore, we illustrate how huge but rare single char ge pair errors in the FMM inflate the error for some of the charges.