Algorithm Design and Implementation for Parallel Scientific Computation

这个项目应用了由偏微分方程式所支配的科学问题所产生的并行算法设计理论问题。大部分工作仅限于解决算法问题，包括网格生成和划分。这个项目开发了用于解决高度非结构化的科学问题的算法和代码，其解决方案可能会随着时间的推移而迅速变化。因此，重点放在并行网格生成算法上，该算法将与系统解算器一起在并行机上运行。该项目还将继续提高线性系统解算器的并行效率，并将扩大关于组合方法的工作，以便为线性系统解算器构造良好的预条件器。这些都被用来加速迭代法的收敛速度。该项目为网格生成和预条件构造等问题设计新算法时采用的一个中心方法是利用这些问题的图形具有可以快速找到的小分隔符的事实。在NSF部分支持的以前的项目中，发现并开发了算法来将有限元网格划分为大约两个相等大小的部分，方法是移除少量单元。这项工作被称为隔板的几何方法。几何方法可以快速地为有限元网格生成可证明是良好的划分。本项目旨在展示网格生成方法和分离器技术的作用如何颠倒。特别是，正在开发使用分离器技术的良好的网格生成方法。这项技术还将用于构建良好的迭代方法来求解这些基本系统。通过实验和分析的方法对几何分离算法进行了进一步的改进。几何方法和其他已知的算法和方法之间的关系正在研究中，如光谱。

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.