Facing Autotools

One of the essential features of a good software package is that it is both portable and straightforward to build.  When working on a system (Linux or even OS X) with a UNIX shell, the most common build tools are the dreaded Autotools.  I say dreaded from a developer’s perspective.  From a user’s perspective, it’s usually only takes invoking

./configure && make

to build a well-designed software package.

On the developer’s end, there’s the seemingly Byzantine world of autoconf, automake, auto-whatever and the unfamiliar world of M4 macros and under the hood magic. At first, when faced with setting up a portable build system, I tried to roll my own using Lua scripts. It worked quite well … until other people needed to use it. When that happened, things started to fall apart under the weight of all of the contingencies I had to keep track of, so I dove into the world of Autotools.

Going through the manuals and trying to understand the terminology with no reference points is incredibly frustrating. I managed to get a decent understanding of how things works, but I still wasn’t able to setup a build system to handle the complicated structure of LuaAV. Fortunately, John Calcote has just published a book called Autotools: A Practitioner’s Guide to GNU Autoconf, Automake, and Libtool. I highly recommend it. It’s clear, explains the terminology well, and is as much of a pleasure to read as such things can be.

Posted in Software Engineering | Tagged , , , | Leave a comment

Fast Multipole Method

To get a better intuition for how the Fast Multipole Method (FMM) approximates n-body interactions, I implemented the equations in Mathematica along with the exact solution. Below are some plots for different situations.  The thing to keep in mind is that the FMM is valid only a certain distance from the center of the particle cluster, so it’s expected that the approximation will not be accurate in that region.

The first row shows contour plots of clusters of 3 and 40 points and a difference between them.  With the difference plot, I was trying to get a sense of how the potential field varies under differing conditions.

The second row is again for 3 and 40 points with a difference.  The cutoff spike in the difference surface is an artifact of numerical evaluation.  Since the potential in 2D is logarithmic, near the particles it tends to blow up.  The coloring of the surfaces follows the phase of the potential.  With 3 particles, there potential wave has 3 clear periods while with 40 particles, it starts to get noisier (an artifact of sampling), but there are likewise 40 periods.  The reason the number of particles matches the number of cycles is from the linear summing of the phase term.

The last row shows the electrical field as derived from the complex potential.  The two images are for 3 particles with the one on the left being exact and on the right calculated from the FMM method.  These plots only show the calculation of the multipole expansion.  To actually implement the FMM as a solution of the n-body problem, someadditional techniques for manipulating the multipole expansion are required.

The FMM simplifies the n-body problem by relating clusters of particles to other clusters of particles.  As the multipole expansion shows, the affect on the potential field a cluster of particles generates can be easily calculated.  The trick now is to figure out how to incorporate the multipole expansion into a hierarchical data structure without having to recalculate it at every single level.  Instead, what we’d like to do is calculate the multipole expansion at the lowest level and accumulate the expansions up the hierarchy through a simple summing of terms.  The problem is that each low-level expansion is centered at a different point, so we need to be able to translate the expansions to the center of higher-level (parent) cells.

The translation lemma shows how to accumulate the multipole expansion into coarser clusters, which can dramatically speed up the calculation for faraway clusters.  This is the bottom up step of the FMM technique.  As has been emphasized a number of times, however, the multipole expansion is only valid for well-separated clusters that are a certain distance from each other.  This means that only clusters that are faraway can be treated this way or, alternatively, we can reduce the size of the clusters in order to apply the technique to closer in clusters.  In order to do this, each box in the hierarchy is given an interaction list..  The interaction list says which boxes interact with each other.  The interaction list consists of all of the child nodes of the neighbors of a box’s parent node not bordering it.

At each level, the interaction list covers a smaller and more refined area of the space.  Any area not covered by the interaction list, which is essentially those boxes at the finest level bordering the box under consideration, are calculated using the O(N^2) n-body method directly, but these calculations should be quite minimal.

In the diagram above, the pink box affects affects the blue boxes.  In order to make use of the multipole expansion, the expansion within the blue boxes has to be recentered on the pink box since expansions can only be summed in a simple way if they are centered on the same location.  This process is described as converting a multipole expansion into a local expansion where local is the pink box.

Once this calculation is done, we have a description for the effects of every particle outside the box, except for those nearest neighbors, and can evaluate their effects simply by plugging in the locations of the particles in the box into the sum of all of the multipole expansions.  This sounds like a lot of work compared to the O(N^2) formulation, but for thousands or millions of particles, it’s vastly more scalable.  The trickiest part is all of the bookkeeping that has to be done to shift the multipole expansions around the space and up and down the spatial hierarchy.  The payoff though, once it’s encoded in a easy to use software package should be significant and we won’t have to think about the hairy details so much anymore and can get to figuring out what massively detailed particle simulations can be used for in terms of spatial composition.

Note: The lemmas posted above were taken from Greengard and Beatson, A Short Course in Fast Multipole Methods.

Download: FMM Mathematica Files

Posted in Computational Technique, Research Literature | Tagged , , , | Leave a comment

N-Body Problems

N-Body problems inevitably come up when doing any most any kind of physical simulation work, particularly when particles are involved.  N-Body problems appear whenever the particles in a system construct a field that in turn determines their dynamics.  The classic examples are typically gravitational, but the n-body problem equally applies to electrostatic, electromagnetic, fluid dynamics, and even acoustic scattering problems.  All can be formulated in essentially the same way just with different constants.

At first sight, n-body problems have a runtime complexity of O(N^2) since every particle interacts with every other particle.  While this is not a big deal for small numbers of particles on the order of a few hundred, the amount of calculations required quickly exceeds what even the speediest of computers can handle.  The challenge is to somehow reduce the complexity to something like O(N log N), which is actually tractable for millions or even billions of particles, making something like the Millenium Simulation Project possible.

Fortunately, there has been a lot of work done in this area since the late 80′s and 90′s for cosmological and electrostatic simulations, particularly by Greengard and Rokhlin.  Together, they developed the Fast Multipole Method (FMM), which makes use of the math of complex analysis of harmonic functions to reformulate the n-body problem as O(N log N).

While this might sound complicated, the essential insight is straightforward and rather enlightening.  The simplification the FMM is based on recognizes that the field a clusters of particles generates, when viewed from a certain distance, can be simplified to a single point that approximates the actual field.  It’s akin to performing a simulation of the earth and sun where the mass of each body is taken to be at a point located the center of mass instead of spread out in space in a sphere.

FMM

The above images were generated using the FMM technique.  The red points in the middle are the particles, each with an equal charge.  The surface represents the potential generated by the points withe the coloring representing the phase.  With one particle, there’s one cycle of a wave around the place.  With 7 particles, there are more cycles as the waves generated by each particle interfere.  The FMM approximation is akin to a spatial wavelet transform.  This is the 2D case.  In 3D, the FMM method uses spherical harmonics to approximate the potential.

While the above surfaces represent electrical potential, what we actually want is the electric field.  The electric field gives the forces acting on the particles and is used to update the simulation.  Fortunately, the electric field can be derived directly from the potential by taking its derivative.  This works because we’re working with complex numbers.  With purely real numbers, the phase information is missing, and the electric field cannot be determined without phase.

One useful way to think about simulations is in terms of Lagrangian and Eulerian paradigms.  The Lagrangian perspective is essentially that of the particle.  Information moves through space according to the dynamics involved.  The Eulerian perspective is of a lattice or field, where fixed discrete points in space sample the dynamics.

In the case of the FMM, the n-body problem is simplified by converting the usual Lagrangian formulation into a hybrid Lagrangian-Eulerian algorithm where clusters of particles become instead waves in space.  This conversion only holds a certain distance away from the cluster, so nearby particles must be treated in an purely Lagrangian manner.

This technique is of course not new.  Spectral methods are used in all kinds of ways to quickly process point-wise spatial information, but such techniques have yet to be placed in the context of spatial composition where there is a continuum between field and particle.  FMM lies at the boundary between the two, and it will be interesting to see how working with the diametrically opposed conceptualization of spatial information can be brought together in a rigorous yet intuitive manner.

References:

Posted in Computational Technique, Research Literature | Tagged , , , , , , | Leave a comment

Chemical Automata

I first came across Chemoton (Chemical Automaton) Theory a few months ago when reading a paper entitled Software Replica of Minimal Living Processes, and ever since it has been an inspiration.  At the time, I was trying to figure out how I could possibly build a system that spanned the range of complexity from Chemistry to a minimal Biology.  I was going off of Walter Fontana’s incredible Algorithmic Chemistry work, trying to find a way that his Lambda Calculus approach could become spatial.  It was Ganti’s Chemoton Theory that finally got me there.

Incredibly, the publication of Chemoton Theory in 1971 and subsequent refinement in the early 70′s was practically simultaneous with Maturana and Varela’s Autopoiesis work and Manfred Eigen’s RNA Hypercycles Theory.  Chemoton Theory, unlike Autopoiesis, is based on a very precise model, though simplified, model of chemistry.  In recent years, Ganti has even gone so far as to detail what actual chemical reactions could possibly realize a Chemoton.  Autopoiesis provides no such precision although the work of Pier Luigi Luisi has taken it much further in that direction.

A Chemoton is a network of 3 autocatalytic cycles: the metabolic (energy), template replication (information), and membrane (boundary/dynamics).  Together, they model a minimal living entity as they meet Ganti’s basic criteria of a living system:

  • it’s an individual unit
  • it performs metabolism
  • it’s inherently stable despite constant transformation
  • it has an information subsystem that programs the whole
  • it’s processes are regulated and controlled

I’m, of course, leaving out a lot of the details so this may not seem like a full definition of a living system.  For the complete explanation, see Ganti’s paper Biogenesis Itself or even better his book The Principles of Life.

What’s most intriguing about the Chemoton from a worldmaking standpoint is it’s fluid nature.  Chemical reactions function best in a fluid environment where spatiality is subsumed by chemical concentrations and statistical tendencies.  There doesn’t need to be a strict spatial ordering for Chemotons to function, just the appropriate chemical concentrations bounded inside a membrane.

Chemoton Theory shows in precise detail how to go from chemistry to a minimal biological unit, but it doesn’t say much about the structure of the membrane or how networks of membranes might form into more complex biological structures.  In the end of Chemoton Theory vol. 1, Ganti speculates about how computers might be built from such objects, but doesn’t link it to Morphogenesis or Topobiology.

Posted in Research Literature | Tagged , , | Leave a comment

worldmaking

worldmaking is a site dedicated to exploring how to make worlds: spaces and systems that accumulate complexity.  The site weaves together the spaces of computation, cybernetics, poetics, mathematics, biology, among others, through observations, musings, and, above all, software experiments and techniques.  The best way of knowing is making.

Posted in General | Leave a comment