Designing lower-dimensional regular arrays for algorithms with uniform dependencies

Abstract

In this paper, we will propose a polynomial-time method to design m-dimensional regular arrays for n (n greater than or equal to m + 1) dimensional algorithms with uniform dependencies, regular algorithms. The proposed method has two steps: the first one is to transform an independently partitioned regular algorithm to a new one, which has an identity dependence matrix. We call this step identity transformation, which is an affine one. In the second step, we propose a spacetime mapping in a fixed form to map the new regular algorithm to a lower-dimensional regular array. Thus, an affine spacetime mapping is constructed by combining the identity transformation and the fixed form's spacetime mapping together. With the proposed affine spacetime mapping, the original regular algorithm can be mapped to a lower-dimensional regular array in polynomial time, which depends only on the number of dimensions of the regular algorithm. Meanwhile, the designed regular array is asymptotically optimal in time and space. (C) 1996 Academic Press, Inc.