Christopher L. Martin
Research Apprentice, 1993 NPAC REU Program
Physics, Chemical Physics, and Mathematics Major, Rice University
Paul D. Coddington
Project Leader, NPAC, Syracuse University
paulc@npac.syr.edu
James R. Allwright
Visiting Assistant Professor,
School of Computer and Information Science, Syracuse University
A system for modeling random surfaces that can evolve with time, specifically for computer simulations of String Theory, requires a fast and efficient means for coloring the sites to ensure that adjacent sites are not updated simultaneously. Effective coloring algorithms are implemented on two different parallel architectures and tested for efficiency.
An example of a string theory random surface whose vertices the parallel algorithms will color.
This algorithm proved to be the most efficient in terms of number of colors required to color the graph and in the amount of time it took to complete the coloring. It works by letting the vertices with the greatest number of neighbors color themselves first, since they would probably be the hardest to color in the long run. These vertices also have the greatest influence on the rest of the set, since they are the most connected. A visualization of the algorithm appears below, as well as comparisons to inferior algorithms.
The largest-degree-first algorithm.
The average number of colors needed for various algorithms implemented in the CM5.
Research paper "Coloring of Triangulated Random Surfaces" in Bogucz, E.A., and Weinman, V.E., editors, "Journal of Undergraduate Research in High-Performance Computing," Volume 3, NPAC technical report SCCS-576, November 1993.