Parallel Euclidean distance matrix computation on big datasets *

We propose, in this paper, three parallel algorithms to accelerate the Euclidean matrix computation on parallel computers. The first algorithm, designed for shared memory computers and GPU, uses a linear index to fill the block lower triangular part of the distance matrix. The linear index/subscripts conversion is obtained with triangular number and avoid loops over blocks of columns and rows. The second algorithm (designed for distributed memory computer) in addition to linear index uses circular shift on a 1D periodic topology. The distance matrix is computed iteratively and we show that the number of iterations required is about half the number of processors involved. Numerical experiments are carried-out to demonstrate the performances of the proposed algorithms