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部分支持的先前项目中，算法 被发现并发展到分割，例如， 通过移除少量元素，将其分成大致相等大小的两块。 这项工作被称为分离器的几何方法。 的 几何方法快速产生可证明的良好分区的有限元 网眼 本项目旨在展示如何网格生成的作用 方法和分离器技术可以颠倒。 特别是，良好的网格 正在开发使用分离器技术的产生方法。 这 技术也将用于构造良好的迭代方法， 解决这些底层系统。 目前正在进一步改进 通过实验和分析的几何分离器算法 方法. 几何方法与 正在研究其它已知的算法和方法，例如谱算法。