Ashby, Thomas J. ;
Kennedy, Anthony D. ;
Watt, Stephen M.
Coxeter Lattice Paths
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 labourintensive 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 = {18624405},
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 