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.
What the authors attempt to is to use this idea to construct ‘translation’ operators, similar to the ones used in FMM, from sampled potential values. That is, they do not explictly use multipole or similar expansions, but attempt to construct equivalent ones from samples. This is also not entirely a new idea. Sharad Kapur and David Long used a similar idea in their SVD based fast solver. What appears to be new in the present paper is that the authors propose to a spherical nonuniform grid — nonuniform both in the radial and in the angular directions. The resulting algorithm is very similar to FMM, apparently with a lower constant.

I do have some questions about this and I wrote to Dr. Boag about a week ago asking the same. Unfortunately, he has not responded to my mail. So I am posting the same questions here (you might want to read the paper before continuing):

  1. Although they show the existence of an NG scheme using global interpolation and implicitly give error bounds, they don’t provide any such bounds for the local schemes that are actually used in their implementation. Have they derived any rigorous bounds? [I can see why it might be possible.]
  2. When they use the local interpolation scheme, the interpolators are constructed only for the target surfaces, by which I assume the surfaces of the boxes in the interaction list of a given box. If this assumption is correct, what happens when the oct-tree is full or nearly full? Wouldn’t they need an awful lot of sampling points in such a case? Wouldn’t a global scheme be more efficient in such a situation?
  3. In the paper, they consider only conductors. If there are dielectric objects present, they would need to evaluate the normal field, which has more rapid variation. What modifications to the sampling rate will be necessary to ensure accuracy in the field?
  4. The presence of dielectrics also brings up another issue. Since the electric field is discontinuous across a dielectric boundary, they will have to ensure that the neighborhood of a given target point has enough samples that do not cross the boundary to make the interpolations work. Unless I misunderstand the algorithm, this would require very careful (read potentially expensive) construction of NG and also increased sampling. How would the overall performance then compare with the more traditional FMM?
  5. In the discussion on numerical results, they compare the accuracy and performance with FMM (FastCap?). Quote (p3568) “[…] our algorithm with zero-order expansion is comparable in terms of accuracy with the FMM of first order.” I think that this statement is a little misleading, because the zeroth-order expansion [interpolation] is on a function whose 1/r dependency has been removed [the paper says that 1/r in Eqn(A1) is taken care of analytically]. So in effect, since they use linear interpolation[p3568], the order of approximation is at least one (because for P=0, r. Phi(r) in Eqn (A1) is a constant).

As I said earlier, this is an interesting idea from an academic point of view. But I doubt if the returns, the potential gains in speed, is worth the effort from a commercial point. Although they claim that the algorithm can be incorporated into existing MoM codes, item 4 above makes it a difficult proposition because of the expensive preprocessing required [unless I have completely misunderstood the algorithm].

But it is good to see newer approaches appearing in academic literature!