Author(s)

E. T. Ong, K. M. Lim & H. P. Lee

Abstract

The Fast Fourier transform on multipoles (FFTM) method is developed for efficient solution of the boundary element method. The method employs the multipole/local expansions to approximate the far field potentials, and uses the fast Fourier transform (FFT) to accelerate the translations of the multipole to local expansions due to its convolution nature. This paper reports the results of using the FFTM algorithm for solving large-scale three-dimensional electrostatics field problems. It is demonstrated that the method can give accurate results both in terms of the calculated capacitance and the surface charge density distributions. It is also found that FFTM has computational complexities of O(Na), where a ranges from 1.0 to 1.4 for the computational time, and from 1.1 to 1.2 for the memory storage requirements. Keywords: electrostatics analysis, capacitance calculation, fast Fourier transform, multipole expansions, fast boundary element method. 1 Introduction In the design of high performance integrated circuits, electronic packaging [1] and micro-electromechanical devices [2], electrostatic analysis of complicated three-dimensional multi-conductor systems is required to determine the functionality of the design. Boundary element method (BEM) [3] is a useful numerical tool to perform such analyses. However, the conventional BEM generates a dense linear system, which requires O(N3) and O(N2) operations when solved using direct methods, such as Gaussian Elimination, and iterative

Keywords

electrostatics analysis, capacitance calculation, fast Fourier transform, multipole expansions, fast boundary element method