The tensor product of bulk synchronous parallel algorithms
Summary
A Bulk Synchronous Parallel (BSP) algorithm is a type of parallel algorithm where communication and computation is separated. We present a way to generalise BSP algorithms for linear functions to a BSP algorithm for the tensor product of linear functions. This is applied to the discrete Fourier transform in higher dimensions, yielding a novel parallel algorithm.