Separators in Two or More Dimensions and Parallel Algorithm Design

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

The goal of this research project is to understand how to design fast and processor-efficient algorithms with an emphasis on algorithms that are targeted toward fine-grain parallel architectures. The approach will be to solve mostly graph theoretic problems that arise from the solution to more concrete problems such as finding approximate solutions to partial differential equations using the finite element method. Almost all of this work assumes that the underlining graphs possess some further geometric or topologic structure, with the hope of finding fast and processor-efficient algorithms for problems which otherwise seem hard to parallelize efficiently. Processor-efficient algorithms will be developed for constructing graph separators which arise in sparse linear systems. These separators will then be used in the construction of more efficient direct and iterative methods for solving these systems. The relationship between graphs obtained using geometric constraints and those obtained using topological constraints will be studied. The bulk of the research will be in the design of processor- efficient parallel algorithms for abstract machines that possess a message passing architecture, such as the Parallel Random Access Machine. Many of the parallel algorithms that have been developed are efficient and simple enough that, when machines are available that can efficiently perform message passing, there should be substantial speedups. The next one or two generations of parallel machines will be able to handle the large amount of traffic generated by the pointer-based algorithms. Algorithms will be designed for the Parallel Random Access Machine model augmented with unit cost operations such as prefix-sum or scan. Algorithms for the augmented model should be simpler, and thus have a better chance of efficient implementation on the newer machines.