Lattice computers for approximating Euclidean space
John Case, Dayanand S. Rajan, Anil M. Shende · Journal of the ACM · 2001
In the context of mesh-like, parallel processing computers for (i) approximating continuous space and (ii) analog simulation of the motion of objects and waves in continuous space, the present paper is concerned with which mesh-like interconnection of processors might be particularly suitable for the task and why. Processor interconnection schemes based on nearest neighbor connections in geometric lattices are presented along with motivation. Then two major threads are exploded regarding which lattices would be good: the regular lattices , for their symmetry and other properties in common with continuous space, and the well-known root lattices , for being, in a sense, the lattices required for physically natural basic algorithms for motion. The main theorem of the present paper implies that the well-known lattice A n is the regular lattice having the maximum number of nearest neighbors among the n -dimensional regular lattices. It is noted that the only n -dimensional lattices that are both regular and root are A n and Z n (Z n is the lattice of n -cubes. The remainder of the paper specifies other desirable properties of A n including other ways it is superior to Z n for our purposes.