Say you want to flip a perfect coin, but the only coins available are imperfect. First, let’s consider the case where we don’t know the details of the available coins, and would prefer not to measure them.

The simplest strategy is to flip a bunch of coins and determine whether the total number of heads is even or odd. As long as there’s a reasonable number of both heads and tails, the probability of an even number of heads will be close to one half.

Here is a measure of “coin perfection” which behaves additively with respect to the parity algorithm:

$$G(p)=-\mathrm{log}|2p-1|$$

I.e., if you have two coins with probabilities of heads $p$ and $q$, and $r$ is the probability that flipping both coins gives the same result, then

In particular, $G(0)=G(1)=0$ and $G(1/2)=\mathrm{\infty}$ as one would expect; flipping a deterministic coin gets you no closer to perfection, and flipping a single perfect coin makes the parity perfectly random regardless of the other coins.

If we know the exact probability of heads $p$, we can do better than this and produce a perfect coin in a finite expected number of flips. By information theory the best we can hope for is $1/H(p)$ where

$$H(p)=-p\mathrm{lg}p-(1-p)\mathrm{lg}(1-p)$$

is the entropy of the coin. Unfortunately determining the exact minimum appears rather complicated, so I’m not going to try to finish the analysis right now.

Imagine that you throw a ball in the air, and lands on the ground and stops (i.e., the collision is inelastic). What happened to the energy and momentum? The answer for energy is completely different from that for momentum, which is a trivial but interesting illustration of the differences between them. Also we get fun with infinities.

Assume a ball of mass $m$ and velocity $v$ hits the ground and stops. Before it hits, it has energy $\frac{1}{2}m{v}^{2}$ and momentum $mv$. After it hits, the energy and momentum of the ball are both zero, so by conservation they must have gone elsewhere.

Momentum is easy: the momentum went into the ground. This is possible without the ground having noticeably moved, since the ground’s mass is some huge value $M\approx \mathrm{\infty}$. The resulting velocity of the ground is the minute $mv/M\approx 0$, but this zero is canceled out by the huge mass to get the finite momentum $Mmv/M=mv$. Thus, it is perfectly consistent to model the ground as a rigid body with infinite mass, zero velocity, and nonzero momentum $p$. Only 3 new variables are required to account for this ground momentum and make our system closed with respect to conservation of momentum.

Energy is different: it is impossible to transfer energy to a large, rigid object. The kinetic energy of the ground after the impact is
$$\frac{1}{2}M{\left(\frac{mv}{M}\right)}^{2}=\frac{{m}^{2}{v}^{2}}{2M}\approx 0$$
In other words, $M=\mathrm{\infty}$ and $V=0$ give $\frac{1}{2}M{V}^{2}=\mathrm{\infty}00=0$ since the zeros outnumber the ones. It is impossible to store energy in the ground by moving it as a whole.

What happens instead is that the energy goes into smaller scale phenomena, typically sound waves or heat. Both cases involve small amounts of matter moving extremely rapidly, which we can roughly characterize as mass $0$, velocity $\sqrt{\mathrm{\infty}}$. The key is that we can store as much energy as we like in these tiny phenomena without ever making a dent in momentum, since $0\sqrt{\mathrm{\infty}}=0$.

We can summarize this situation as follows:

It is possible to hide momentum in a large, motionless object without expending any energy.

It is possible to hide energy in a bunch of small objects without using any momentum.

The fact that energy hides in small places makes it harder to deal with in general; there a lot of small places, which is why the law of conservation of energy has been modified many times to account for new terms no one had previously noticed. Momentum is simpler: if you lose some momentum, all you have to do is look around for the gigantic object (e.g., the Earth).

Currently, we (or at least I) don’t know how to do multigrid on general problems, so we’re stuck using conjugate gradient. The problem with conjugate gradient is that it is fundamentally about linear systems: given $\mathrm{Ax}=b$, construct the Krylov subspace $b,\mathrm{Ax},{A}^{2}x,\dots $ and pick out the best available linear combination. It’s all in terms of linear spaces.

Interesting human scale physics is mostly not about linear spaces: it’s about half-linear subspaces, or linear spaces with inequality constraints. As we start cramming more complicated collision handling into algorithms, these inequalities play a larger and larger role in the behavior, and linearizing everything into a CG solve hurts.

Enter multigrid. Yes, it’s theoretically faster, but the more important thing is that the intuition for why multigrid works is less dependent on linearity: start with a fine grid, smooth it a bit, and then coarsen to handle the large scale cheaply. Why shouldn’t this work on a system that’s only half linear? There are probably a thousand reasons, but happily I haven’t read enough multigrid theory yet to know what they are.

So, I predict that eventually someone will find a reasonably flexible approach to algebraic multigrid that generalizes to LCPs, and we’ll be able to advance beyond the tyranny of linearization.

A few days ago I was in another discussion where someone raised the question of why presidential elections are so close. In the interests of avoiding these discussions in future, here’s a histogram of the popular vote margin over all presidential elections (data from [1]):