Optimal parallel selection in sorted matrices

We present a parallel algorithm running in time O(logmlog*m(loglogm + log(nlm))) time and O(mlog(nlm)) operations on an EREW PRAM for the problem of selection in an m x n matrix with sorted rows and columns, m less than or equal to n. Our algorithm generalizes the result of Samath and He (1992) for selection in a sorted matrix of equal dimensions, and thus answers the open question they posted. The algorithm is work-optimal thus improving upon the result in (Samath and He, 1992) for the case of square matrices as well. Our algorithm can be generalized to solve the selection problem on a set of sorted matrices of arbitrary dimensions.