Parallel Algorithms for Geometric Problems

点击翻译按钮获取中文摘要

The goal of this project is to investigate the design of parallel algorithms for geometric problems, both for shared- memory (PRAM) models and the (more realistic) network models. The network models of interest include the situation where the number of processors available p is fixed (i.e., does not depend on the size n of the problem being solved). In such a framework, one needs to bring into the picture the sequential "front end" to the parallel machine, since the parallel machine is too small to even store the problem being solved. Thus the techniques used are both parallel and sequential, since a substantial part of the computation may take place in the sequential machine. Attention will be given to problems that are still open within the traditional frameworks (i.e., assuming massive rather than limited parallelism), with special emphasis on problems whose solution would impact the parallel complexity of many geometric problems (for example, multisearching and matrix searching). The project will also initiate investigation of parallelism for computational algebraic geometry and geometric modeling. The research undertaken involves implementations on commercially available parallel hardware.