A High-efficiency Implementation of Fast Multipole Boundary Element Method

Although the fast multipole boundary element method [1] developed by the authors is theoretically known to be O(N logN) complexity where N denotes the degrees of freedom, our first implementation have shown the com-plexity only to be reduced to O(N1.3) in the best case. Thus we thoroughly revised every algorithm, including non-numeric operations such as cell data structure con-struction, so that any of them would not exceed the com-plexity of O(N logN). The revised algorithms were re-alized by a new implimentation with shared memory par-allel scalability. The performance investigation of the new imple-mentation results: 1) Single-processor time versus N is demonstrated to match the theoretically predicted O(N logN) complexity per iteration. 2) Required mem-ory footprint is demonstrated to be virtually O(N) and about 12 Kbytes per boundary node. 3) The parallel ef-ficiency of 0.89 at 8 processors is achieved on a shared-memory multiprocessor system. 1