License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06271.8
URN: urn:nbn:de:0030-drops-7695
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/769/
Go to the corresponding Portal

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

Coxeter Lattice Paths

pdf-format:
06271.AshbyThomas.Paper.769.pdf (0.2 MB)

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:DagSemProc.06271.8,
  author =	{Ashby, Thomas J. and Kennedy, Anthony D. and Watt, Stephen M.},
  title =	{{Coxeter Lattice Paths}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/769},
  URN =		{urn:nbn:de:0030-drops-7695},
  doi =		{10.4230/DagSemProc.06271.8},
  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
Collection: 06271 - Challenges in Symbolic Computation Software
Issue Date: 2006
Date of publication: 25.10.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI