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

亲爱的艾尔，亚历克斯一直让我了解情况，因为你和他都集中在我们拟议的分区和排序方法的修订范围上，这些方法利用系数大小的知识，而不仅仅是系数结构。感谢您对这项工作的支持，这项工作的成果可以直接提供给其他几个项目。为了在进一步处理这笔拨款之前完成我认为你需要的东西，他和我将该项目抽象为以下两段，供同行和非技术性读者使用。我希望这是可以的。David==========================================================================解决方案-PDE的自适应网格划分和变量排序亚历克斯·波滕和大卫·E·凯斯提出者考虑了网格划分和变量排序问题，这些问题是在非结构网格上离散的偏微分方程组模拟的问题的并行计算中出现的。在早期的工作中，已经开发了分区算法，该算法在保持处理器之间的负载平衡的同时，为分布式存储器并行性带来较低的通信成本。这里提出了解自适应分区方法，该方法努力在这样的数据并行环境中获得良好的收敛速度。每次迭代的通信量可能会增加，但对于中等粒度的并行来说只是小幅增加，而更重要的每次迭代的消息启动数量应该不会受到太大影响。针对局部划分问题的快速求解，提出了解自适应排序方法。最近开发的两类已被证明在非自适应环境中成功的划分和排序算法将在本提案的划分和排序阶段中占据突出地位。一类是谱算法(即利用网格和离散化算法得到的拉普拉斯矩阵的某个特征向量的近似的算法)，而第二类包括多层算法。这两种算法都将被推广到解自适应的环境中。科学和工程中的许多计算问题可以用偏微分方程组来建模，然后用定义在非结构网格上的代数方程组来求解。对于这类问题，最自然的并行形式需要将原始域分解成子域，子域被整体映射到单独的处理器上。迭代区域分解算法自然地适合于这个框架，其中解是由子问题组装而成的，子问题的边界条件是通过在最近邻居之间传输有限数量的信息来设置的。这里提出的划分和排序方法对于这种区域分解类型的解方法将是有用的，该区域分解类型的解方法是考虑到当代分布式存储器计算机中的高通信计算成本比而设计的。在这项工作中可以利用的关键机会是协同结合两个单独成熟的想法，通常被用作“黑箱”--仅基于稀疏结构的划分和排序，以及基于对系数中所反映的物理相关性的理解的域块迭代。在这项工作中开发的软件工具将针对空气动力学和地球物理等应用领域的“重大挑战”问题进行演示。

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.