Optimal parallel selection in sorted matrices

Hong Shen; Sarnath Ramnath

doi:10.1016/0020-0190(96)00100-7

Optimal parallel selection in sorted matrices

Hong Shen, Sarnath Ramnath

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

We present a parallel algorithm running in time O(log m log^{(Black star)} m (log log m + log(n/m))) time and O(m log(n/m)) operations on an EREW PRAM for the problem of selection in an m × n matrix with sorted rows and columns, m ≤ n. Our algorithm generalizes the result of Sarnath 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 (Sarnath 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.

Original language	English
Pages (from-to)	117-122
Number of pages	6
Journal	Information Processing Letters
Volume	59
Issue number	3
DOIs	https://doi.org/10.1016/0020-0190(96)00100-7
Publication status	Published - 12 Aug 1996
Externally published	Yes

Keywords

EREW PRAM
Parallel algorithms
Selection
Sorted matrix
Time complexity

Access to Document

10.1016/0020-0190(96)00100-7

Cite this

@article{bbff4bc8d9c0488cb0b58fac8b44f51e,

title = "Optimal parallel selection in sorted matrices",

abstract = "We present a parallel algorithm running in time O(log m log(Black star) m (log log m + log(n/m))) time and O(m log(n/m)) operations on an EREW PRAM for the problem of selection in an m × n matrix with sorted rows and columns, m ≤ n. Our algorithm generalizes the result of Sarnath 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 (Sarnath 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.",

keywords = "EREW PRAM, Parallel algorithms, Selection, Sorted matrix, Time complexity",

author = "Hong Shen and Sarnath Ramnath",

year = "1996",

month = aug,

day = "12",

doi = "10.1016/0020-0190(96)00100-7",

language = "English",

volume = "59",

pages = "117--122",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Optimal parallel selection in sorted matrices

AU - Shen, Hong

AU - Ramnath, Sarnath

PY - 1996/8/12

Y1 - 1996/8/12

N2 - We present a parallel algorithm running in time O(log m log(Black star) m (log log m + log(n/m))) time and O(m log(n/m)) operations on an EREW PRAM for the problem of selection in an m × n matrix with sorted rows and columns, m ≤ n. Our algorithm generalizes the result of Sarnath 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 (Sarnath 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.

AB - We present a parallel algorithm running in time O(log m log(Black star) m (log log m + log(n/m))) time and O(m log(n/m)) operations on an EREW PRAM for the problem of selection in an m × n matrix with sorted rows and columns, m ≤ n. Our algorithm generalizes the result of Sarnath 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 (Sarnath 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.

KW - EREW PRAM

KW - Parallel algorithms

KW - Selection

KW - Sorted matrix

KW - Time complexity

UR - http://www.scopus.com/inward/record.url?scp=0042094784&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(96)00100-7

DO - 10.1016/0020-0190(96)00100-7

M3 - Article

AN - SCOPUS:0042094784

SN - 0020-0190

VL - 59

SP - 117

EP - 122

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

Optimal parallel selection in sorted matrices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this