Parallel Monotone Spline Interpolation and Approximation on GPUs

Publisher:
CRC Press
Publication Type:
Chapter
Citation:
Designing Scientific Applications on GPUs, 2014, pp. 295 - 310
Issue Date:
2014
Full metadata record
Files in This Item:
Filename Description Size
Parallel monotone spline interpolation and approximation on GPUs.pdfPublished version465.69 kB
Adobe PDF
Monotonicity preserving interpolation and approximation have received substantial attention in the last thirty years because of their numerous applications in computer aided-design, statistics, and machine learning [9, 10, 19]. Constrained splines are particularly popular because of their exibility in modeling di erent geometrical shapes, sound theoretical properties, and availability of numerically stable algorithms [9,10,26]. In this work we examine parallelization and adaptation for GPUs of a few algorithms of monotone spline interpolation and data smoothing, which arose in the context of estimating probability distributions. Estimating Cumulative Probability distribution Functions (CDF) from data is quite common in data analysis. In our particular case we faced this problem in the context of partitioning univariate data with the purpose of e cient sorting. It was necessary to partition large data sets into chunks of approximately equal size, so that these chunks could be sorted independently and subsequently concatenated. In order to do that, empirical CDF of the data was used to nd the quantiles, which served to partition the data. CDF was estimated from the data based on a number of pairs (xi; yi); i = 1; : : : ; n, where yi was the proportion of data no larger than xi. As data could come from a variety of distributions, a distribution-free nonparametric fitting procedure was required to interpolate the above pairs. Needless to say the whole process was aimed at GPU, and hence the use of CPU for invoking serial algorithms had to be minimized.
Please use this identifier to cite or link to this item: