Obtaining Exact Solutions from Approximate Solutions: A Class of Paradigms for Parallel Computation

目前正在进行的研究遵循并行计算的两种范式：约简范式和分而治之的范式。简化范例如下进行：给定大小为n的问题实例，它使用简化过程来产生小于或等于n/2的大小的问题实例，从而可以容易地从简化问题的解中推导出原始问题的解。关于减少范例的工作延续了国际和平研究所以前成功开展的一条研究途径。关于分而治之范式的工作也有类似的前景。在这些范例下完成的工作都是通过从近似解获得精确解来进行的。PI知识渊博，在所提议的领域内是一位有成就的研究人员。所提出的工作对并行计算的未来具有非常重要的意义，并可能产生实质性的影响。

Research is in progress that follows two paradigms for parallel computation: A reduction paradigm and a divide and conquer paradigm. The reduction paradigm proceeds as follows: given a problem instance of size n it employs a reducing procedure to produce a problem instance of size less than or equal to n/2, such that the solution to the original problem can be easily deduced from the solution to the reduced problem. Work on the reduction paradigm continues a previously successful avenue of research carried out by the PI. Work on the divide and conquer paradigm holds similar promise. Work done under each of these paradigms proceeds by obtaining exact solutions from approximate solutions. The PI is very knowledgeable and is an accomplished researcher in the area proposed. The work proposed is very significant for the future of parallel computation and has potential for substantial impact.