Algorithms and Bicycles

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
• Comments

(more…)

 

Pam Frost Gorder, “Multicore Processors for Science and Engineering”, IEEE Computing in Science and Engineering, March/April 2007, pp3–7

A very informal review/introduction to the possible impact of the modern multicore CPUs such as Intel Core 2 Duo and IBM Cell processor. The subject of the paper becomes especially significant in the context of Intel’s demonstration of the 80 core CPU:

http://www.intel.com/research/platform/terascale/teraflops.htm?iid=homepage+80core

I think the development of these processors is going to change the way we look at electromagnetic problems. Currently, when we try to solve an EM problem, we formulate into some integral equation, then discretize it using MoM and then we develop the algorithms to solve it efficiently. I think this must change: I propose that after formulating the integral equation and before discretization, we will have to look at the architecture of the system where it is going to be solved. We will have to tailor our discretization and solution methodologies to match the architecture.

This is a paper worth reading for an overview. Thanks to my colleague and friend, Dr. Andy Mathis for getting me a copy of it.

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…)

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…)