Ganesh Swami

One of the papers nominated for the best paper award at Supercomputing 06 is titled “Scalable Algorithms for Molecular Dynamics Simulations on Commodity Clusters” from the DE Shaw Research group. If your standard of a modern molecular dynamics code is Computer Simulations of Liquids, then this paper is definitely worth a look. I’ve summarized the innovations below:

Midpoint method

Published earlier this year in the Journal of Chemical Physics, this is a parallelizing algorithm which is a hybrid between spatial decompositions and force decompositions. The major innovation of this method is the reduced communication bandwidth, which can be a problem when you scale simulations to hundreds of computers.

Bitwise Time Reversibility

One of the most important requirements for an integrator solving Newton’s equations of motion is symplecticity. One way to check to check for this is by running your integrator in negative time. Doing so should return the system to the initial state. Though not an absolute requirement, this is a nice thing to have for minimizing the energy drift, which ultimately leads to a more realistic simulation. These guys have an integrator that does this.

Constraints in single precision

To reduce high frequency motions (like vibrations of Carbon-Hydrogen bonds for example), simulations typically make use of constraints to hold bond lengths or atom velocities fixed. Typical codes RATTLE and SHAKE need to be done in double precision for accuracy and to maintain energy conservation. This paper talks about the use of an (unpublished) algorithm that is stable in single precision.

Normalized local coordinates

Instead of representing coordinates in an absolute global frame, these guys normalize coordinates. This gives them more precision (due to operations done on floating points of the same magnitudes.) It also makes handling periodic boundary conditions simple. Another advantage they mention is that doing pressure control is time reversible.

Interpolation schemes

Personally, I think this is the cornerstone of the paper. The paper mentions that instead of interactions being a function of distance between the particles, they compute it as a function of . The advantage is that the same set of polynomial coefficients can be used for computing both forces and energies.

SIMD instructions

I’m just mentioning this for completeness. As far as I know, every high performance engine makes use of these instructions. In fact, GROMACS has hand tuned kernels written using these instructions. In theory, this makes your code four times faster.

In conclusion, I was pretty impressed with the quality of work and the innovations these guys have brought to the community. Download the paper here.

I was recently pulled over by the Web 2.0 police for the inappropriate use of tags and categories. When I initially setup Wordpress, I decided to use categories to tag my posts. This wasn’t elegant - the number of categories quickly got out of hand.

After reading a bunch of sites around the web, I still can’t figure out the difference. This shouldn’t be so hard, but I’m impatient. So, I’ve settled on an aggregate of what ever I’ve read on the web. I’m going to use categories to broadly classify and tags to pick out the keywords from the post. These tags are also going to be added as meta keywords to the head of each post.

The new mantra: Category = Classification. Tag = Keyword.

Two other things I’ve done:

• An AJAX archive browser.
• Significantly cleaned up the sidebar. Less is more.

You’ve probably heard by now that the stock price of Google has crossed the five hundred dollar mark.

A couple of months back, I attended a talk by Dr. Prabhakar Raghavan. This was right after he was hired to lead the Research & Development for Yahoo! He spoke about a bunch of stuff, but the subject of advertisement pricing is what I found most interesting.

In 1996, James Mirrles and William Vickerey won the Nobel prize in Economics for coming up with the idea of Vickerey auctions in decision theory. The problem with ordinary auctions is that a big player can easily outbid a small player. Imagine the fair market price of a divisible commodity being $500, but a big player uses his monetary strength to outbid everyone by bidding for $1000. This might outprice the commodity for the small players making them less likely to compete. What would the auctioneer rather have: one sale at $1000 or ten sales at $500, the true market price?

The Vickerey method uses the second highest bid as the fair market price of the commodity.

From Google’s perspective, it doesn’t have to follow the Vickerey style strictly by the book. Instead it can pick a price midway between the first and second highest bids. This has a direct impact on the GOOG top line (revenue.)

For a fair perspective, you’ll also have to look at how other players in the market are doing. The management at the other big player in the market, YHOO posted less than spectacular results recently. You could attribute this to poor execution on Yahoo’s part, but the top brass also commented on the general poor performance of the overall market. This is key.

The cynic in me asks: Is GOOG screwing over the market for short term gain? If that’s so, will the Efficient Market Hypothesis re-adjust the market and dictate a slowdown in growth rate for GOOG over the next few quarters?

Is my reasoning correct, or am I missing something fundamental here?

A recent article by Coleman on exploiting structure for portfolio optimization is an eyeopener for realtime optimization. The article talks about decomposing a dense matrix into a diagonal matrix and a linear term. The diagonal matrix can be solved in linear time as opposed to polynomial time for the full dense matrix.

Symmetry can also be used in speeding up particle dynamics. Routines like molecular and celestial dynamics propagate in time by solving Newton’s equations of motion. If every body interacts with every other body in the system, the interaction graph of N bodies will be a complete graph , ie with edges. Simple implementations will store the interactions in the graph’s square adjacency matrix of size N, with entries. The use of Newton’s third law

allows us to populate just half the matrix. This results in a huge increase in speed (either for simulation or control.) I’ve created a contour plot of a symmetric random matrix with zeros along the diagonal to demonstrate the fact.

Further reductions can be made in mechanical systems with symmetry. If the set of canonical transformations on the phase space is a symmetry group, leaving the Hamiltonian invariant, then the equations of motion can be brought down to a lower dimension space of orbits of the symmetry group. Why re-calculate something that isn’t going to change?

Further, if the equations of motion are invariant under a set of transformations (either in space or time), then conservation laws are realized. This is Noether’s Theorem.

In conclusion, though disguised most times, structure and symmetry show up in problems all the time. This post was inspired by rod’s post on the fenews article. Thanks!

One of my favorite minor-modes in emacs is the flyspell-mode. It continuously marks all words not found in the ispell-dictionary as you type. It’s particularly useful with AucTeX because it skips comments and TeX markup.

If you want to invoke flyspell-mode everytime you go into LaTex-mode, add this hook to your .emacs file:

(add-hook 'LaTeX-mode-hook 'flyspell-mode)