Parallel Algorithms for Geometric Problems

这个项目的目标是研究几何问题的并行算法设计，包括共享内存（PRAM）模型和（更现实的）网络模型。感兴趣的网络模型包括可用处理器数量p是固定的情况（即，不依赖于正在解决的问题的大小n）。在这样的框架中，需要考虑到并行机的顺序“前端”，因为并行机太小，甚至无法存储要解决的问题。因此，所使用的技术是并行的和顺序的，因为大部分计算可能在顺序机器中进行。将注意在传统框架内仍然开放的问题（即，假设大量而不是有限的并行性），特别强调其解决方案将影响许多几何问题的并行复杂性的问题（例如，多重搜索和矩阵搜索）。该项目还将开始研究计算代数几何和几何建模的并行性。所进行的研究涉及商用并行硬件的实现。

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.