Algorithm Design and Implementation for Parallel Scientific Computation

并行科学计算的算法设计与实现

• 批准号: 9505472
• 负责人: Gary Miller
• 金额: $ 31.38万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-07-01 至 1999-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9505472&HistoricalAwards=false
• 关键词: Algorithm; Design; Implementation; Parallel; Scientific

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.

该项目应用了由部分微分方程控制的科学问题引起的平行算法设计理论问题。 大部分努力仅限于解决算法问题，包括网格生成和分区。 该项目为解决高度非结构化的科学问题而开发了算法和代码，其解决方案可能会随着时间而迅速改变。 因此，重点放在平行网格生成算法上，该算法将与系统求解器一起在平行机上运行。 该项目还继续提高线性系统求解器的并行效率，并将扩展组合方法的工作，以构建用于线性系统求解器的良好预处理。 这些用于加速迭代方法的收敛速率。 该项目用于设计新算法的一种中心方法，用于诸如网格生成和预处理构建等问题，是要使用以下事实：这些问题的图形具有很小的分离器，可以很快找到。 在NSF部分支持的先前项目下，发现并开发了分区的算法，例如，通过删除少量元素，将有限元网格到大约两个相等大小的零件中。 这项工作称为分离器的几何方法。 几何方法迅速为有限元网格提供了可证明的良好分区。 该项目旨在展示如何逆转网格生成方法和分离器技术的作用。 特别是，正在开发使用分离器技术的良好网状生成方法。 该技术还将用于构建良好的迭代方法来解决这些基础系统。 通过实验和分析方法，在几何分离器算法中正在进一步改进。 正在研究几何方法与其他已知算法和方法（例如光谱）之间的关系。