A reaction-diffusion
computation was implemented by dividing space into tiny blocks, and in each
solving a chemical reaction iteratively, adding diffusion afgter each
iteration. Concentrations were initially specified in the east half of this
grid so as to evolve into a spiral wave, the same concentrations were
replicated in reverse order on the west half, so the concentration field
had exact mirror symmetry in the double-precision numerical array. This
exactness is way better than you could get in any real experiment or in some
imaginary computer with real-valued (as opposed to floating-point)
concentrations and spatial positions. The symmetry is demonstrably perfect. So
the evolution of this pattern must proceed perfectly symmetrically as
the computation advances. Only it didn't. One spiral grew at the expense of the
other. The mirror symmetry did not persist.How could this be, in a finite
computation where the data are exactly the same on both sides and so are
the equations of evolution? And how could one side rather than the other become
the Chosen One to preferentially grow?
Was
there a mistake in the programming? If so, it would induce the same errors on
both sides, operating as it does on the exact same numbers. That could not
upset the initial symmetry.Maybe, then, there was a mistake in prescribing that
initial symmetry: maybe one of the grid-points had concentration not quite
equal to its counterpart on the other side of the line. Hardly possible, if you
made the right-side pattern by simply copying the left-side numbers onto the
right. Did the copying go wrong then? To check this, you can subtract every
number on the left from its counterpart on the right and see if you get
anything but zeros in the 16-bit answers. You don't.So now you guess this
symmetry must be somehow dynamically unstable, like a pencil standing
upright on its point, or a snowball poised on the top of a hill trying to
decide which way to roll down. Maybe, as in nature, here some infinitesimal
atomic fluctuation starts a growth avalanche that determines which way it will
go. Maybe so, but there are no infinitesimals in a digital computer, only
binary 1s and 0s: there are no tiny fluctuations to get this snowball rolling
downhill. Then it must be that the hardware makes an occasional mistake, and
this is the seed of an asymmetry that grows under the action of the prescribed
chemical kinetic equations that maybe represent an unstable situation. Maybe
here we have discovered a sensitive detector of rare single-bit mistakes,
perhaps caused by cosmic rays or cockroaches in the power supply or something.
But you can do the computation over and over, save the results, and subtract
them to see if you get all 0s: the result comes out exactly the same every
time, right down to the last digit or bit in every grid-point. No mistakes.
Mystery.
What more can we ask, or do we just have to accept that the ways of such
complex machines are inscrutable? Well, we can try boiling the phenomenon down
to simpler and simpler instances until the asymmetry ceases to erup, or the
instance gets transparently simple and I say "Aha!".In my experience
the problem kept simplifying without any change in its essence until it came
down to adding just three numbers. Let's call them a, b, and c.
They
represent a concentration b in a grid point at some distan ce from the mirror
plane, and the one the next closer, a,and the one next farther, c. All three
are involved in pattern evolution, because what goes on in one cell is affected
by concentrations in its immediate neighbors. If I add them in order a plus b
then plus c,as my numerical procedure scans across the grid, I get some result.
As the algorithm scans on to the other side of the mirror, it encounters these
three concentration again but in the opposite sequence, and adds them c plus b
then plus a. Surely the order of adding doesn't matter: this is the
"associative law of arithmetic", that we disdained to attend in
textbooks because it seems a pompous triviality. Of course adding a to b
is the same as adding b to a. We have to get the same result, else banks
could not use computers to reliably do our monthly checkbook statements:
results would depend on the order of adding individual checks, and would come
out differently if checks are sorted by serial number or by date of writing or
by date of clearing, and if they were added in increasing or decreasing order
in those lists. Well that is exactly what happens here!
How
can that be? Well, digital computers do necessarily use exactly binary 1s and
0s to represent numbers, but the rules are sometimes tricky. "Surely not
so tricky as to violate associativity! " you say. But what if your numbers
are not exactly 0 or 1 or 2 ... or 2^16 ? What if they are for example 0.001 or
2,000,000.3? Then you want the computer to represent them as best it can
(rounding off where necessary) like 6.57583 x 10^ some integer power. This is
floating-point arithmetic. Round-off errors then occur. Banks work only in
integers representing cents, I guess, but scientists must approximate real
numbers. So? That is still not sufficient excuse for a violation of
associativity or of symmetry, because the round-off errors should be the same
on both sides of the mirror plane, should they not?. But watch carefully. Is
the roundoff the same when we add same numbers in different orders? Here comes
a silly example that shows it doesn't have to be:
Call
"eps" the smallest number such that 1. + eps > 1..Adding anything
smaller to 1. results in a round-off that hides the change. There has to be a
number this small, and it is not so small as to be unrepresentable in the
machine: just use a slightly more negative integer exponent in its
representation. Now consider such a still smaller number, e.g.,eps' = eps/2,
and try adding
that
to 1. and to -1. in either of two orders:
(eps'+1.)
-1. = 1.-1. = 0 but in opposite order (-1. +1.) + eps' = 0 + eps' = eps' > 0.
ooops.
This
example is ridiculous because in most real science problems, and certainly in
the one considered above, we would be summing adjacent numbers of comparable
size, and so would not encounter an increment so small that it gets rounded off
instantly. But it should be taken as a caution that what we expect from
arithmetic theorems, even so fundamental a theorem as the associative law, is
not always realized in a digital computer. Now we better look around for a realistic
example, or look at exactly what happened in every register of the computer in
some specific (a+b)+c <> (c+b)+a example.Let's write a simple program to
add up some different numbers in forward order and in reverse order and see if
we get the same result.I pick some random simple expression to specify the
numbers: each is 3/3000 plus 0..9 /3000, so the answer should be exactly
75/3000, but it isn't quite. It is off by about 1 millionth of that amount, and
differently according to the order of summing the same ten numbers! I use the
language C; you might use BASIC or whatever you prefer:
#include
"stdio.h"
int i;
float b, c;
void main(void)
{
for (i=0; i<10; i++) { /*
enough steps tp cause some overflows */
b
+= (3+i)/3000.; /* arbitrary formula */
c
+= (3+ 9-i)/3000.; /* same thing in reverse */
printf("%d
%16.18f %16.18f\n", i,b,c);
/* final b
"should" = c = 75/3000 = 0.025*/
}}
results:
0 0.001000000047497451 0.004000000189989805
1 0.002333333482965827 0.007666666992008686
2 0.004000000189989805 0.010999999940395355
3 0.006000000052154064 0.013999999500811100
4 0.008333333767950535 0.016666665673255920
5 0.011000000871717930 0.018999999389052391
6 0.014000000432133675 0.020999999716877937
7 0.017333334311842918 0.022666666656732559
8 0.021000001579523087 0.024000000208616257
9 0.025000002235174179 0.025000000372529030
not same, in
the end, and not 0.025, but off by two different amounts about one millionth
this size. The errors (from cumulative overflows) differs according to your
arbitrary choice of the sequence in which to add. This dependence of the answer
on the order of summing the same numbers (all of comparable magnitude) provides
the seed of asymmetry that kicked off enlargement of one spiral at the expense
of the other. As it happens (I tried the same experiment in the chemical
laboratory) asymmetry grows in real nature too, though there the seed is
provided in another way. By accident the computer produced a phenomenon
qualitatively like nature. But it was only an accident. It doesn't give a good
interpretation of the time it takes for the instability to occur. And it
wouldn't have happened at all had I run the computation not using floats, but
using, for example, 16-bit integer precision to represent concentrations. The
machine is perfectly error-free and deterministic, and so is the software, yet
it produces (identically in every trial, but not identically between
mirror-image trials) discrepancies from the sums it ought to get. I didn't
think this was possible, but following the observed anomaly revealed this
surprise anyway.
This unexpected
subtlety may have a bearing on a surprising symmetry “discovered” in
computations of 3d vortex rings analogous to the spirals mentioned above. In a
certain situation these rings develop wiggly asymmetries, but two cases did
not: a pair of initially perpendicular rings, each one with 180-degree rotation
symmetry, each linking the other twice, and a rings preserved their initially
symmetry as long as I computed. Why the exceptions? Well, both have the
symmetry of the numerical grid (a cubic lattice) whereas the other cases had,
for example, 3- or 5-fold rotation axes. So their identical parts fell on the
grid at different orientations, allowing the ever-so-slight difference between
a discrete grid and a perfect continuum to introduce discrepancies
between otherwise symmetrically identical parts. If the symmetry is
unstable, these discrepancies grow exponentially ... except in the case that
the discrepancy is strictly zero. Even if it was initially zero, it might
become otherwise after the first few iterations, if diffusion from neighboring cells
is tallied up in a different order due to the concentration fields being
reflected while the algorithm proceeds in fixed sequence through the cube
regardless of its contents. Does the fact that no asymmetry grew up reveal that
symmetry is in fact stable in this case, or that the associativity error is
somehow not the right thing to seed such a growth in this case? That could be
answered by repeating the 3d computation with some different small asymmetry
deliberately added, but I haven't done it yet.
PS: the triplet of perpendicular rings are inextricably
entangled in the Borromean way. The unit glides along the cube’s
body diagonal, along which both the grid and the IC have
3-fold symmetry. But when I cut out the object and rotated
it to upright (so it might thereafter glide through the
floor-ceiling periodic BC), the 3-fold symmetric IC clashed with the
4-fold symmetric numerical grid, and the symmetry-breaking
instability was triggered.