Algorithm Design and Implementation for Parallel Scientific Computation

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

This project applies parallel algorithm design theory problems arising from scientific problems governed by partial differential equations. Most of the effort is restricted to solving algorithmic problems including mesh generation and partitioning. This project develops algorithms and code for the solution of scientific problems that are highly unstructured and whose solution may be rapidly changing with time. Thus, the emphasis is on parallel mesh generation algorithms that will run on parallel machines in conjunction with the system solvers. The project also continues to improve the parallel efficiency of linear system solvers and will extend the work on combinatorial approaches to the construction of good preconditioners for linear system solvers. These are used to speedup the convergence rate of iterative methods. A central approach taken by this project for the design of new algorithms for problems such as mesh generation and preconditioner construction is to use the fact that the graphs for these problems have small separators that can be quickly found. Under prior projects partially supported by NSF, algorithms were discovered and developed to partition, for instance, finite element meshes into roughly two equal size pieces by removing a small number of elements. This work is referred to as the geometric approach to separators. The geometric approach quickly produces provably good partitions for finite element meshes. This project intends to show how the role of mesh generation methods and separator technology can be reversed. In particular, good mesh generation methods are being developed which use the separator technology. This technology will also be used in the construction of good iterative methods for solving these underlying systems. Further improvements are being made in the geometric separator algorithms via experimental and analytic methods. Relationships between the geometric method and other known algorithms and methods, such as spectral, are being investigated.