Search Results

Documents authored by Kennedy, Anthony D.

Coxeter Lattice Paths

Authors: Thomas J. Ashby, Anthony D. Kennedy, and Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

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.

Cite as

Thomas J. Ashby, Anthony D. Kennedy, and Stephen M. Watt. Coxeter Lattice Paths. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

  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 =		{},
  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}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail