"Colorings for Efficient Derivative Computation on Grids with Periodic Boundaries"
D. W. Cranston and P. D. Hovland
Preprint Version: [pdf]
Computing the first derivatives of a discretized nonlinear partial differential equation (PDE) can be made more efficient given colorings of the lattice points of the plane, cylinder, or torus that assign different colors to all vertices within some specified stencil. Goldfarb and Toint showed how to efficiently color the lattice
points of the plane, but their results do not extend to the cases of cylinders or toruses, as arise in the case of discretizing PDEs with periodic boundary conditions on a Cartesian grid. We give colorings for the (4l −3)-point star and the l×l square stencils (for all l) in the plane, on the cylinder, and on the torus. We also give colorings for the (6l−5)-point star in Z3 and for the l×l×l cube in Z[sup 3] with periodic boundary conditions in 0 and 1 dimensions. We show that all colorings are optimal or near-optimal.