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.
STANFORD