Ref: Weiping Shi, Jianguo Liu, Naveen Kakani, Tiejun Wu, “A fast hierarchical algorithm for three dimensional capacitance extraction,” IEEE Trans. Computer Aided Design of Integrated Circuits and Systems, vol. 21, No. 3 March 2002
I like this work. Yes, it has severe limitations and the authors make ridiculous claims. Yet, the idea is fairly sound within the context of the target problems.
Essentially, this is a variation on Appel’s classic algorithm. To explain the idea, let us consider the simple case of a rectangular box in free space. It has six faces and let us refer to them as panels A1..A6. The algorithm starts by assuming that the charge is uniformly distributed on each of these panels. Then, consider two panels Ai and Aj. If the potential coefficient between Ai and Aj is smaller than a specified bound, then Ai and Aj are allowed to interact directly. If not, the larger panel, say Ai, is divided into two. Then, the potential coefficient between the children of Ai and Aj are computed and compared as before. This procedure is recursively continued.
In the end, the algorithm constructs a binary tree representation of the object. The unknowns in the problem are the leaf nodes of the tree. Matrix vector products are then computed using tree traversals very similar to that of FMM.

Obviously, this algorithm is fast. In fact, for lower accuracy, they show that it is several times (often 50-60 times) faster than FMM. It also has a lower memory requirement. These are good properties.

But there are obvious limitations too. To begin, the algorithm implicitly assumes that the geometric shapes can be represented using a few flat polygonal surfaces. It may be possible to modify it to accommodate higher order surfaces, but it is hard. As a result, problems involving curved surfaces will require a large number of smaller panels, leading to inefficiency (note that the first step of the algorithm requires m*m potential evaluations, where m is the initial number of panels). However, for the class of applications that they have in mind, modeling of integrated circuits, this is not an issue.

Secondly, there is no tight error control. Effectively, they are using a 0-th order multipole expansion. So I suspect that for very badly conditioned problems (throw in a very thin dielectric with a high relative permittivity between two conductors), this method could be a suspect as far as accuracy is concerned.

Thirdly, the authors claim that the algorithm requires only the potential evaluations. They make this claim based on the assumption that dielectrics can be accommodated in the Green’s function. This is true only if dielectrics can be assumed to be of infinite extent (layered media problems). If there are dielectric objects of finite extent, say a vertical support of cylindrical shape, the algorithm collapses.
Despite all these disadvantages, it is certainly a simple and interesting idea. A paper I would recommend for reading at bed time(unless you are married or have a partner…).