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.

For the last couple of weeks, I have been trying to understand the so called loop-tree and loop-star basis functions used in CEM. I had a very simple case implemented in bbmm, but that was only tested at higher frequencies. Last week, I started testing it at very low frequencies, down to about 3Hz, on simple geometries. It produced nonsensical results. Naturally, intense debugging followed.

(more…)

This site is not about  politics or morality. I am not an environmental activist either. Yet, I am forced to write about a technological development that is disturbing me from exactly those perspectives. The object of my current dilemma is the recently reported wirelessly powered television.

It is a fascinating technology, although, as an electrical engineer, not surprising. James Maxwell and Michael Faraday would have just nodded at the development.

What bothers me is the power consumption. Commercially available 32″ LCD televisions consume anywhere from 90W to 140W according to a CNET comparison. Now, that is not an insignificant number, compared to that of smaller electronic devices like cell-phones.

According to one report, 25% of the energy is lost in transmission when one such wireless technology is used. And, according to Sony’s own press release, their transmission efficiency is only 60%. So, if we take the power consumption of a 32″ LCD television to be 100W, the actual power needed to operate it wirelessly is about 166W if we were to use Sony’s technology. The lost power is more than sufficient to light a small room in a house, let alone the number of smaller devices that can be charged with it.

The world is currently scrambling for energy. One of the root causes of the two wars this country is  currently fighting  can be traced to our need for cheap energy, in one form or another. There are millions of people around the world who do not have electricity  for their basic needs.

As someone who has spent much of his adult life studying electromagnetic theory,  I like the theoretical elegance  of wirelessly transmitted power.  However,  I am asking myself: would it be moral for me to use this technology in my home?

After years and years of development — so to speak — I just released the FMM accelerated MoM solver that I have been working on. As the name indicates, it is a barebone solver, with direct and iterative matrix solvers. The FMM kernel has some nice features, including a new 3-component EFIE formulation for loop-tree. They are not available by default because I haven’t tested them as much as I want to. May be in the coming days.

I am off to a two week vacation in India! Some warm days for a change!

In the last three weeks or so, I have received three e-mails from one Mr.Vedran Kordic from a website called “INTECHWEB.ORG”. It came to my Acceleware address. The first e-mail said this:

Dear Dr. Velamparambil,

My name is Vedran Kordic and I am contacting you regarding the In-Tech new book project under the working title “Microwave and Millimeter Wave Technologies”, ISBN 978-953-7619-X-X.

Based on your paper “GPU Accelerated Krylov Subspace Methods for Computational Electromagnetics” you are nominated to submit proposal for the book chapter. You are however neither limited to the paper topic nor we are asking you to republish the above paper. This paper served as a proof that you are doing a high quality research.

(more…)

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

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