Last week, I read the following paper:
Amir Boag and Boris Livshitz, “Adapative Nonuniform-Grid (NG) Algorithm for Fast Capacitance Extraction”, IEEE Trans. Microwave Theory and Techniques, vol 54, No. 9, Sept. 2006, pp3565-3570.
To begin, I like the idea from an academic point of view. The authors’ primary objective is to construct a technique that has the same asymptotic complexity as that of the static FMM (O(n)) but with a smaller proportionality constant. The central idea used in the development is the following: at sufficiently large distance from a set of finite sources, the potential is a smooth function, and therefore can be interpolated to any given precision. That is, given the potential at a set of points, say sampling points, sufficiently far away from the source, one can accurately compute the potential at a new point in the vicinity of the sampling points by interpolating from the known values. This is common knowledge. (more…)