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

亲爱的Al， Alex一直让我了解情况，因为你和他已经在我们提出的研究分区和排序方法的修订范围上取得了一致，这些方法利用了系数大小的知识，而不仅仅是系数结构。感谢您对这项工作的支持，其成果可以直接用于其他几个项目。为了完成我认为您在进一步处理这笔拨款之前需要完成的工作，他和我将该项目摘要为以下两段，供同行和非技术读者使用。我希望没有问题。Alex Pothen和David E. Keyes提出了在非结构化网格上离散的偏微分方程建模的问题并行计算中出现的网格划分和变量排序问题。在早期的工作中已经开发了分区算法，该算法在保持处理器之间的负载平衡的同时，为分布式内存并行性带来了较低的通信成本。本文提出了求解自适应划分方法，力求在这种数据并行环境下获得良好的收敛率。每次迭代的通信量可能会增加，但对于中等粒度的并行性来说，通信量只会适度增加，而更重要的每次迭代的消息启动数量不应该受到严重影响。为了快速求解局部分区上的问题，提出了自适应排序方法。最近开发的两类分区和排序算法已被证明在非自适应环境中是成功的，它们将在本提案的分区和排序阶段中发挥重要作用。一类由谱算法组成（即，利用从网格和离散化过程中导出的拉普拉斯矩阵的某个特征向量的近似值的算法），而第二类包括多层算法。这两种算法将被推广到解自适应环境。科学和工程中的许多计算问题都可以用偏微分方程来建模，并随后作为在非结构化网格上定义的代数方程系统来解决。这类问题最自然的并行形式要求将原始域分解为子域，这些子域整体映射到单个处理器上。迭代域分解算法自然适合这个框架，其中解决方案是由子问题组成的，子问题的边界条件是通过在最近的邻居之间传输有限的信息来设置的。本文提出的划分和排序方法将有助于求解此类领域分解类型的方法，这些方法是针对当前分布式存储计算机中较高的通信与计算成本比而设计的。在这项工作中被利用的关键机会是协同地连接两个已经独立成熟的思想，并且通常被用作“黑盒”——仅基于稀疏结构的划分和排序，以及基于理解反映在系数中的物理依赖性的领域阻塞迭代。在这项工作中开发的软件工具将在空气动力学和地球物理学等应用领域展示“重大挑战”问题。

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.