next up previous
Next: Morphological processes and Up: Getting started: Programming Previous: Example: Partial differential

Example: Using approximate PDE solutions to organize amorphous systems

We should be able to use the approximate solutions to Laplace's equation to provide a bootstrap process for organizing the geometry of an amorphous computing system, even though we have no a priori knowledge of the actual positions or orientations of communicating neighbors, beyond the assumption of local communication.

In particular, we can solve Laplace's equation in a patch to obtain solutions that are locally orthogonal coordinate functions, by specifying appropriate boundary conditions. These solutions can then be used to assign virtual coordinates to the computational particles in the patch. These virtual coordinates are automatically consistent, and thus can be used as a grid for other mathematical operations. For example, we could use these solutions to construct accurate approximations for differential operators, thus allowing us to start with a random grid and obtain precise answers to PDEs. Given coordinate systems on every patch, we can sew the patches together with overlapping patches and thus make global solutions.

Thus, we can use crude methods for solving partial differential equations to establish a coordinate system for computational particles, and we can iterate this process to obtain as good a coordinate system as we please. We are currently investigating (in simulation) how it may be possible to dynamically adjust the simulated (or physical!) positions of the processors to optimize the error accrued in the solution process.

This example highlights an important general point: In amorphous computing we are forced to develop computational techniques that are only slightly dependent on the physical processor arrangement and interconnect. This restriction serves as an intellectual lever for the development of novel algorithms for solving hard problems. For example, since we are forced to establish and refine our coordinate systems based on the results of computation, we have a natural basis for doing dynamic multigridding, a technique that can be used to attack a large class of currently intractible problems in physics and engineering.



next up previous
Next: Morphological processes and Up: Getting started: Programming Previous: Example: Partial differential



Gerald Jay Sussman
Thu Jun 27 16:56:19 EDT 1996