Adaptive Multilevel Iterative Substructuring Methods

在椭圆型偏微分方程中，解是非局部的：它在任何一点的值取决于任何其他点的右侧。这样的方程出现在流体力学和固体力学中。此外，实际问题通常在某些地方具有不规则（快速变化）的几何形状或材料属性，并且在离散化之后，会导致非常大的问题，特别是在3D中；数以亿计的自由度不再是那么罕见了。由于问题的规模，使用分布式大规模并行计算机是强制性的，无论是处理器能力还是内存空间。迭代子结构方法是一类领域分解方法，设计用于使用大规模并行计算机来解决这类问题，尽管解决方案是非局部性的。本项目将从本课程中最先进的方法之一BDDC方法开始，该方法只需要代数信息（子结构的矩阵）。子结构方法是可扩展的处理器数量达到一定程度；在此之后，需要在处理器之间协调解决的粗问题的直接解的复杂性将占主导地位。在这个项目中，该方法本身被递归地应用，并产生了一个多级方法，就像在多重网格中一样，只是从一开始就自然地适应了并行处理。使用自适应技术将使不规则问题的稳健处理成为可能，该技术将计算工作集中在需要的地方。在大规模并行计算机上进行物理模拟的有效算法具有重要的战略意义。计算模型在很大程度上增加并取代了工程中昂贵的、可能危险的或不可行的物理实验。计算能力的显著增长现在是通过使用更多的并行处理器来实现的。该项目将开发有效使用大量处理器的新方法。它还将有助于对大规模并行算法的数学理解，这是必不可少的，因为它允许人们保证它们将在更多的处理器和其他问题上工作，而不是目前可以测试的问题。

In an elliptic partial differential equation, the solution is non-local: its value at any point depends on the right-hand-side at any other point. Such equations arise in fluid and solid mechanics. In addition, real problems have often irregular (quickly varying) geometry or material properties in some places, and, after discretization, result in very large problems, particularly in 3D; hundreds of millions of degrees of freedom are not so unusual any more. Because of the size of the problem, the use of distributed massively parallel computers is mandatory, both for processor power and for the memory space. Iterative substructuring methods are a class of domain decomposition methods devised to use massively parallel computers for such problems in spite of the non-locality of the solution. This project will start from one of the most advanced methods of this class, the BDDC method, which requires algebraic information only (the matrices of the substructures). Substructuring method are scalable with the number of processors up to some point; after that, the complexity of direct solution of the coarse problem, needed to coordinate the solution between the processors, will dominate. In this project, the method itself is applied recursively and results in a multilevel method much like in multigrid, except naturally adapted to parallel processing from the outset. Robust treatment of irregular problems will be made possible by the use of adaptive techniques, which focus computational work in the places where it is needed.Efficient algorithms for physical simulations on massively parallel computers are of strategic importance. Computational modeling is augmenting and to a large extent substituting expensive and possibly dangerous or infeasible physical experiments in engineering. Significant growth of computational power is now achieved by using more processors in parallel. This project will develop new methods to use a large number of processors efficiently. It will also contribute to the mathematical understanding of massively parallel algorithms, which is essential because it allows one to guarantee that they will work on more processors and on other problems than they can currently be tested on.