Mathematical Sciences: Solutions-Adaptive Grid Partitioning and Variable Ordering for PDEs

数学科学：解决方案 - 偏微分方程的自适应网格划分和变量排序

• 批准号: 9505110
• 负责人: Alex Pothen
• 金额: $ 14.1万
• 依托单位: Old Dominion University Research Foundation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-08-01 至 1999-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9505110&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Solutions; Adaptive; Grid

Dear Al, Alex has kept me in the loop as you and he have converged on a revised scope of our proposed investigation into partitioning and ordering methods that take advantage of knowledge of coefficient magnitude, instead of coefficient structure only. Thanks for your support of this work, whose outcomes could feed directly into several other projects. To complete what I believe you need before processing this grant further, he and I have abstracted the project into the following two paragraphs for peers and nontechnical readers. I hope it is okay. Best Regards, David ========================================================================== Solution-adaptive Grid Partitioning and Variable Ordering for PDEs Alex Pothen and David E. Keyes The proposers consider grid partitioning and variable ordering problems that come to the fore in the parallel computation of problems modeled by partial differential equations discretized on unstructured grids. Partitioning algorithms that maintain load balance among the processors while incurring low communication costs for distributed memory parallelism have been developed in earlier work. Here solution-adaptive partitioning methods are proposed that strive, in addition, to attain good convergence rates in such data parallel contexts. Communication volume per iteration may rise, but only modestly for moderate-granularity parallelism, while the more important number of message-startups per iteration should not be strongly affected. Solution-adaptive ordering methods are also proposed for the fast solution of the problems on the local partitions. Two recently developed classes of partitioning and ordering algorithms that have proved to be successful in non-adaptive contexts will feature prominently in both the partitioning and ordering phases of this proposal. One class consists of spectral algorithms, (i.e., algorithms that make use of an approximation to a certain eigenvector of a Laplacian matrix derived from the grid and the discretization sche me), while the second class includes multilevel algorithms. Both algorithms will be generalized to the solution-adaptive context. Many computational problems in science and engineering can be modeled by partial differential equations, and subsequently solved as a system of algebraic equations defined on an unstructured grid. The most natural form of parallelism for such problems requires the original domain to be decomposed into subdomains, which are mapped whole on to individual processors. Iterative domain decomposition algorithms fit naturally into this framework, wherein a solution is assembled from subproblems whose boundary conditions are set by transmitting a limited amount of information between nearest neighbors. The partitioning and ordering methods proposed herein will be useful for solution methods of such domain decomposition type, which are designed with respect for the high communication-to-computation cost ratio in contemporary distributed-memory computers. The key opportunity to be exploited in this work is that of synergistically joining two ideas that have matured separately, and are usually used as ``black boxes''-- partitioning and ordering based on sparsity structure only, and domain-blocked iteration based on understanding the physical dependencies reflected in the coefficients. The software tools developed in this work will be demonstrated for ``grand challenge'' problems in application areas such as aerodynamics and geophysics.

亲爱的艾尔，亚历克斯一直让我在循环中，因为你和他已经收敛于我们提出的分区和排序方法，利用系数大小的知识，而不仅仅是系数结构的研究的修订范围。 感谢您对这项工作的支持，其成果可以直接用于其他几个项目。 为了在进一步处理这笔赠款之前完成我认为您需要的内容，他和我将该项目抽象为以下两段，供同行和非技术读者阅读。 我希望这没问题。 最好的问候，大卫=凯斯 提议者考虑网格划分和变量排序问题，在并行计算的问题建模的偏微分方程离散非结构化网格中脱颖而出。在早期的工作中已经开发了分区算法，保持处理器之间的负载平衡，同时产生低通信成本的分布式存储器并行。 这里的解决方案自适应分区方法，提出了努力，此外，在这样的数据并行上下文中，以达到良好的收敛速度。 每次迭代的通信量可能会增加，但对于中等粒度的并行性来说只是适度的，而每次迭代的消息启动的更重要的数量不应该受到强烈的影响。为快速求解局部剖分上的问题，提出了解自适应排序方法。 最近开发的两类分区和排序算法，已被证明是成功的非自适应上下文将突出的特点，在分区和排序阶段的建议。 一类是谱算法（即，利用对从网格和离散化方案导出的拉普拉斯矩阵的特定特征向量的近似的算法），而第二类包括多级算法。 这两种算法将被推广到解决方案自适应上下文。 科学和工程中的许多计算问题都可以用偏微分方程来建模，然后在非结构化网格上求解代数方程组。 对于这些问题，最自然的并行形式需要将原始域分解为子域，这些子域被整体映射到各个处理器上。 迭代区域分解算法自然适合这个框架，其中的解决方案是从子问题，其边界条件是通过传输最近的邻居之间的有限数量的信息。 本文提出的分区和排序方法将是有用的解决方案的方法，这种域分解类型，这是针对高通信计算成本比在当代分布式存储器计算机设计的。 在这项工作中要利用的关键机会是协同地加入两个已经分别成熟的想法，并且通常被用作“黑匣子”-仅基于稀疏结构的分区和排序，以及基于理解系数中反映的物理依赖关系的域阻塞迭代。 在这项工作中开发的软件工具将被证明为“重大挑战”的问题，如空气动力学和地球物理学的应用领域。