A Wideband Fast Multipole Method for the two-dimensional complex Helmholtz equation

A Wideband Fast Multipole Method (FMM) for the 2D Helmholtz equation is presented. It can evaluate the interactions between N particles governed by the fundamental solution of 2D complex Helmholtz equation in a fast manner for a wide range of complex wave number k, which was not easy with the original FMM due to the instability of the diagonalized conversion operator. This paper includes the description of theoretical backgrounds, the FMM algorithm, software structures, and some test runs.Program summaryProgram title: 2D-WFMMCatalogue identifier: AEHI_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEHI_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 4636No. of bytes in distributed program, including test data, etc.: 82 582Distribution format: tar.gzProgramming language: CComputer: AnyOperating system: Any operating system with gcc version 4.2 or newerHas the code been vectorized or parallelized?: Multi-core processors with shared memoryRAM: Depending on the number of particles N and the wave number kClassification: 4.8, 4.12External routines: OpenMP (http://openmp.org/wp/)Nature of problem: Evaluate interaction between N particles governed by the fundamental solution of 2D Helmholtz equation with complex k.Solution method: Multilevel Fast Multipole Algorithm in a hierarchical quad-tree structure with cutoff level which combines low frequency method and high frequency method.Running time: Depending on the number of particles N, wave number k, and number of cores in CPU. CPU time increases as N log N.