Abstract: Our main result is a Θ(log n) time algorithm for selecting the kth smallest element in a set of n elements stored in a 2-dimensional reconfigurable mesh (rmesh) with n processors. First we show that a good approximation of the median can be found in Θ(log log n) time, which can be used to solve 2-dimensional linear programming over n equations in Θ(log n loglog n). <\p>

We also show an Ω(log log n) lower bound for selection, which is the first non-trivial lower bound on the rmesh which does not rely on the bandwidth constraints of the mesh and does not restrict the processor instruction set.

Keywords: reconfigurable mesh, rmesh, selection, median, linear programming, parallel algorithm, parallel computer

Complete paper   A preliminary version of thie paper appeared in Proc. Frontiers `92: 4th Symp. on Frontiers of Massively Parallel Computation (1992), pp. 38-45.

Parallel computing:

An overview of my work in this area, and my papers.
Here is a somewhat whimsical explanation of parallel computing, a tutorial on parallel computing and a list of parallel computing resources

Reconfigurable mesh:

Ultrafast Parallel Algorithms and Reconfigurable Meshes surveys some of our work in this area.

Copyright © 2015-2017 Quentin F. Stout