Glimmer: Multilevel MDS on the GPU

We present Glimmer, a new multilevel algorithm for multidimensional scaling that accurately reflects the high-dimensional structure of the original data in the low-dimensional embedding, and converges well. It is designed to exploit modern graphics processing unit (GPU) hardware for a dramatic speedup compared to previous work. We also present GPU-SF, an efficient GPU version of a stochastic force algorithm that we use as a subsystem in Glimmer. We propose robust termination conditions for the iterative GPU-SF computation based the filtered sum of point velocities. Our algorithms can either compute high-dimensional Euclidean distance on the fly from a set of high-dimensional points as input, or handle precomputed distance matrices. The O(N2) size of these matrices would quickly overflow texture memory, so we propose distance paging and distance feeding to remove this scalability restriction. We demonstrate Glimmer's benefits in terms of speed, convergence and correctness against several previous algorithms for a range of synthetic and real benchmark datasets.