Algorithms and Bicycles

I was studying “FFTSVD: A Fast Multiscale Boundary-Element Method Solver Suitable for Bio-MEMS and Biomolecule simulation” by Altman et. al .

There are a few things that bother me about this paper. First, it is essentially a combination of ideas from  Kapur & Long’s SVD approach, the precorrected FFT, and a variation of the generalized FMM.  They use a low-rank approximation to construct what they call as the “dominant”  sources and responses. This uses a rank-revealing QR decomposition with re-orthogonalization for every box/node in the hierarchical oct-tree structure. Then, in order to integrate the pFFT ideas,  a set of equivalent grid-sources need to be constructed. This needs the evaluation of the potentials at pre-selected observation points and sub-sequently a Moore-Penrose inverse. Again, this needs to be done for every box/node. Essentially, the algorithm requires the setup operations of both pFFT and the SVD approaches. Unless, of course, I have missed something obvious and being dumb.

If my understanding is correct, then this algorithm must be terribly expensive to setup. Curiously enough, the authors do not report any  results on the setup times. Nothing. Zero.

They do, however, report  matrix-vector product timings, which show moderate improvement over existing techniques. Nothing breath-taking there either (less than a factor of 2 at best).

From a user’s perspective, it does not matter if we can get 10 times or 100 times speed-up for matrix-vector timings. What matters is if the over-all time is significantly reduced. Again, there is no report on those timings either.

My question is to the editor and the anonymous reviewers: how could you possibly accept this work without asking the most obvious and most important question? What were you doing?

Oh, well.

I read the following two papers a few weeks ago and found the ideas to be very similar to Rokhlin’s generalized FMM.

• References:

• Hao Gang Wang, Chi Hou Chan, Leung Tsang, “A New Multilevel Green’s Function Interpolation Method for Large-Scale Low Frequency EM Simulations,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol-24, No. 9, September 2005, pp1427-1443.
• Hao Gang Wang, Chi Hou Chan, “The Implementation of Multilevel Green’s Function Interpolation Method for Full-Wave Electromagnetic Problems,” IEEE Trans. Antennas and Propagation, Vol-55, No. 5, May 2007, pp1348–1358

(more…)

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. (more…)

Ref: Ozgur Ergul and Levent Gurel, “Enhancing the accuracy of the interpolations and anterpolations in MLFMA,” to appear in IEEE Antennas and Wireless Propagation Letters (Abstract and pdf files are available from the journal website at IEEE.org)

I was talking to my two year old nephew, Kannan, the other day. We were discussing some of the most recent developments in the field of fast algorithms in computational electromagnetics. Well, he is not exactly an expert in this field, but as soon as I mentioned this paper to him, he asked “Uncle Sanjay, is it not what Drs. Song and Chew developed over ten years ago and what a lot of people have been using since then? I think it sounds like mommy taking grandma’s recipe for chicken curry and claiming it to be her own.” (more…)