Parallel calculation of the median and order statistics on GPUs with application to robust regression
School of Information Technology, Deakin University, 221 Burwood Hwy, Burwood 3125, Australia
arXiv:1104.2732 [cs.DC] (14 Apr 2011)
@article{2011arXiv1104.2732B,
author={Beliakov}, G.},
title={“{Parallel calculation of the median and order statistics on GPUs with application to robust regression}”},
journal={ArXiv e-prints},
archivePrefix={“arXiv”},
eprint={1104.2732},
primaryClass={“cs.DC”},
keywords={Computer Science – Distributed, Parallel, and Cluster Computing, Computer Science – Data Structures and Algorithms, Mathematics – Numerical Analysis, 65Y05, 65Y10, 90C25,, F.2.2, C.1.4, C.1.2, G.4},
year={2011},
month={apr},
adsurl={http://adsabs.harvard.edu/abs/2011arXiv1104.2732B},
adsnote={Provided by the SAO/NASA Astrophysics Data System}
}
We present and compare various approaches to a classical selection problem on Graphics Processing Units (GPUs). The selection problem consists in selecting the $k$-th smallest element from an array of size $n$, called $k$-th order statistic. We focus on calculating the median of a sample, the $n/2$-th order statistic. We introduce a new method based on minimization of a convex function, and show its numerical superiority when calculating the order statistics of very large arrays on GPUs. We outline an application of this approach to efficient estimation of model parameters in high breakdown robust regression.
April 19, 2011 by hgpu
