ABSTRACT
All-pairs computations occur in numerous and diverse applications across many areas. In many-body simulations and molecular dynamics, computation of pairwise gravitational or electrostatic forces is needed to study system evolution [16]. A similar scenario occurs in computational electromagnetics except that the field is sampled in multiple directions, turning this into a vector computation [15]. In the radiosity method in computer graphics, a scene is divided into patches and the reflection and refraction of light between every pair of patches is of interest to compute the equilibrium light energy distribution [14]. In computational systems biology, correlations between pairs of genes are sought based on their expression levels over a large set of observations [32]. Clustering algorithms typically use a distance metric and use all-pairs distances to guide the clustering process [6]. While the details vary, common to these applications is computation between all pairs of entities from a given set.
