Linear programming on the reconfigurable mesh and the CREW PRAM

This thesis presents a new parallel algorithm for solving the linear programming problem in $R sp{d}$ for the reconfigurable mesh architecture and for the CREW PRAM model. The algorithm is based on the sequential technique discovered independently by Megiddo (Meg83, Meg84) and by Dyer (Dye84, Dye86), which gives a linear time algorithm, in n, the number of constraints, to solve the linear programming problem in d variables, when d is fixed. The parallel algorithm runs in O(log$ sp3$n) time in $R sp2$, $O(n sp{1/3}$log$ sp3$n) time in $R sp{3}$ and in $O(n sp{1/2}$) time in $R sp{d}$ on the reconfigurable mesh of size n. A simplified version of the same algorithm runs in O(log$ sp{d}$n) time on the CREW PRAM. The o($n sp{1/2}$) running times achieved by the parallel linear programming algorithm in $R sp{2}$ and $R sp{3}$ are due to a novel selection algorithm, which is also presented in this thesis. The selection algorithm runs in O(log$ sp3$n) time on the reconfigurable mesh. As is the case with the sequential technique, it will be shown that the parallel technique can be applied towards solving other problems such as linear separability, circular separability, digital disk and the Euclidean one-center problem, and can be extended to solve quadratic programming problems, in particular finding the smallest circle separating two sets of points