Computation of 2-dimensional fast transforms and image filtering on transputer networks

The computation of 2-dimensional fast Fourier and cas-cas transforms and image filtering via transform-domain block convolution on transputer networks is discussed. Loosely coupled message-passing architectures require a fairly course-grained algorithmic decomposition. They are therefore in general only suited for multidimensional transforms. The paper considers computation of two-dimensional transforms on a processor farm. Distributed architectures impose certain constraints on the choice of algorithm. The relative merits of row-column and vector-radix algorithms are investigated in the context of a processor farm and it is shown that, despite having higher arithmetic complexity, row-column algorithms are better suited for a processor farm.