Optimal parallel selection in sorted matrices

被引：3

作者：

Shen, H

Ramnath, S

机构：

[1] ST CLOUD STATE UNIV,DEPT COMP SCI,ST CLOUD,MN 56301

[2] ABO AKAD UNIV,DEPT COMP SCI,TURKU,FINLAND

来源：

INFORMATION PROCESSING LETTERS | 1996年 / 59卷 / 03期

关键词：

EREW PRAM; parallel algorithms; selection; sorted matrix; time complexity;

D O I：

10.1016/0020-0190(96)00100-7

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：117 / 122

页数：6

共 50 条

[31] Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches [J].

Lin, Jyh-Jye ;

Chan, Chi-Yuan ;

Wang, Biing-Feng .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (08) :932-942

[32] Architecture independent parallel selection with applications to parallel priority queues [J].

Gerbessiotis, AV ;

Siniolakis, CJ .

THEORETICAL COMPUTER SCIENCE, 2003, 301 (1-3) :119-142

[33] A parallel algorithm for the inversion of matrices with simultaneously diagonalizable blocks [J].

Lazaridis, Dimitrios S. ;

Draziotis, Konstantinos A. ;

Tsitsas, Nikolaos L. .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2024, 174 :340-351

[34] New parallel algorithms for finding determinants of NxN matrices [J].

Almalki, Sami ;

Alzahrani, Saeed ;

Alabdullatif, Abdullatif .

WORLD CONGRESS ON COMPUTER & INFORMATION TECHNOLOGY (WCCIT 2013), 2013,

[35] Fast parallel selection on the linear array with reconfigurable pipelined bus system [J].

Han, YJ ;

Pan, Y ;

Shen, H .

FRONTIERS '99 - THE SEVENTH SYMPOSIUM ON THE FRONTIERS OF MASSIVELY PARALLEL COMPUTATION, PROCEEDINGS, 1999, :286-293

[36] A SIMPLE OPTIMAL PARALLEL ALGORITHM TO SOLVE THE LOWEST COMMON ANCESTOR PROBLEM [J].

LIN, R ;

OLARIU, S .

LECTURE NOTES IN COMPUTER SCIENCE, 1991, 497 :455-461

[37] Some optimal parallel algorithms on interval and circular-arc graphs [J].

Hsu, FR ;

Shan, MK ;

Chao, HS ;

Lee, RCT .

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2005, 21 (03) :627-642

[38] Cost-optimal parallel algorithms for the tree bisector and related problems [J].

Wang, BF ;

Ku, SC ;

Shil, KH .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2001, 12 (09) :888-898

[39] An optimal parallel solution for a geometric matching problem using BSR model [J].

Myoupo, JF ;

Semé, D .

PDPTA'2001: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, 2001, :556-562

[40] Optimal Parallel Quantum Query Algorithms [J].

Stacey Jeffery ;

Frederic Magniez ;

Ronald de Wolf .

Algorithmica, 2017, 79 :509-529

← 1 2 3 4 5 →