Finding the median on a vector computer , by Marta Woodward and Stewart A. Levin

Median and quantile calculations are used in geophysics for discriminating against high amplitude noise bursts. While both plotting and processing applications of the median have been presented in the past by the SEP, the latter have been neglected in practice-in part because quantile calculations have been much slower than mean and variance calculations. This paper discusses the results of a literature search for median and quantile algorithms that are well-matched to array processors and vector computers. Timing comparisons are made between a vectorizable scheme and the nonvectorizable program currently used by the SEP. Although the vectorizable algorithm requires 50% more comparisons to find the median than its nonvectorizable counterpart (3n as opposed to 2n for an array of length n), it runs six times faster on a Convex C1-XP. An algorithm that finds the median with an asymptotic worst case of 3n comparisons is also outlined.


to SEP-56 index page

pdf(517 KB)
ps.gz(742 KB)