Two-Dimensional Convolution on a Pyramid Computer

We give an algorithm for convolving a k x k window of weighting coefficients with an n x n image matrix on a pyramid computer of O(n2) processors in time O(log n + it2), excluding the time to load the image matrix. If [formula omitted], which is typical in practice, our algorithm has a processor-time product O(n2k2) which is optimal with respect to the usual sequential algorithm. A nice feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k. Thus, for convolving two {0, 1 }-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite state.