License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-7695
URL: http://drops.dagstuhl.de/opus/volltexte/2006/769/

Ashby, Thomas J. ; Kennedy, Anthony D. ; Watt, Stephen M.

Coxeter Lattice Paths

pdf-format:
Dokument 1.pdf (229 KB)


Abstract

This talk concerns generating code for running computationally intensive numerical lattice QCD simulations on large parallel computers, using an approach based on the theory of Coxeter groups. Many physical systems have inherent symmetry, and this is usually implicit in the calculations needed to simulate them using discrete approximations, and thus in the associated code. By reversing this and basing the generation of code on the symmetry group of the lattice in question, we arrive at a very natural way of generating and reasoning about programs. The principal aim is a formal way of representing lattices and the paths on these lattices that correspond to the required calculations. This foundation allows the creation and manipulation of lattices and paths to be automated, obviating what can be a labour-intensive and errorprone task. In more detail, a method will be given for representing the points of a regular lattice as elements of the translation subgroup of an affine Coxeter group, by finding the subgroup generators starting from the Coxeter graph of the affine group. Similarly, step sequences are derived as words in the free group generated by the translation subgroup generators themselves. We introduce code generation techniques and the automation of two code optimisations; the grouping of paths into equivalence classes, and the factoring out of common path segments. The latter technique reduces the amount of communication necessary between nodes, and is thus likely to be important in practice.

BibTeX - Entry

@InProceedings{ashby_et_al:DSP:2006:769,
  author =	{Thomas J. Ashby and Anthony D. Kennedy and Stephen M. Watt},
  title =	{Coxeter Lattice Paths},
  booktitle =	{Challenges in Symbolic Computation Software},
  year =	{2006},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt },
  number =	{06271},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/769},
  annote =	{Keywords: Parallel computing, code generation, Coxeter groups, regular lattices, lattice paths, path optimisation}
}

Keywords: Parallel computing, code generation, Coxeter groups, regular lattices, lattice paths, path optimisation
Seminar: 06271 - Challenges in Symbolic Computation Software
Issue date: 2006
Date of publication: 25.10.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI