Integrated Geometric and Algebraic Multigrid Methods

综合几何和代数多重网格方法

• 批准号: 1522615
• 负责人: Jinchao Xu
• 金额: $ 38.5万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1522615&HistoricalAwards=false
• 关键词: Integrated; Geometric; Algebraic; Multigrid; Methods

A primary goal of this project is to create framework for developing more robust and user-friendly solvers for linear systems of equations, which are ubiquitous in science, engineering, and industrial applications. The investigators will carry out integrated analysis and development of geometric multigrid and algebraic multigrid methodologies. Geometric multigrid (GMG) methods form a class of multilevel solvers designed to solve linear systems of equations arising from certain classes of discretized partial differential equations (PDEs). Algebraic multigrid (AMG) methods are also multilevel solvers, though these techniques avoid any dependence on information regarding an underlying grid geometry or PDE. As a result, GMG methods are effective tools for solving a more restricted class of linear systems with a strong theoretical backing for their performance, whereas AMG solvers apply to more general linear systems, though do not share the same mathematical rigor in justifying their performance. This research project will employ functional analysis as a natural framework for studying GMG and AMG methods in a unified setting. The resulting theory will establish strong guiding principles for analyzing and developing robust, efficient, and scalable multilevel solvers. The iterative solvers under development will be implemented in open source parallel codes, made available to a broader scientific computing community, providing powerful tools for simulation and a foundation for future algorithm research and development. Moreover, this project provides Ph.D. students with opportunities to participate in a variety of education and research activities, in which they will receive advanced training, participate in conferences, and collaborate with researchers from industry and Department of Energy laboratories.This research project investigates a unifying framework for analyzing GMG and AMG methods in a functional analysis setting. This framework provides a strong foundation for understanding the operators, relationships between spaces, and other core ingredients involved in these multilevel solvers, such as the construction of coarse spaces and their respective bases, and a convergence analysis that applies to a broad variety of existing AMG methods. Furthermore, for problems originating from discretized PDEs, the integration of geometric information for constructing auxiliary grid-based preconditioners and highly effective smoothers on each level can be seamlessly integrated, allowing for more flexible and aggressive algebraic coarsening. More benefits of incorporating geometric information are realized in nearly optimal load balancing and predictable communication patterns for parallel implementations. For more general linear systems, the project studies the use of (relaxed) compressed sensing techniques to preserve sparsity for coarse space operators, which can be supplemented with information from an underlying geometric grid or adjacency graphs of the matrix to gain control over the computational complexity. It is expected that these techniques will be useful in solving problems with non-quasiuniform underlying grids or problems with matrices that are not symmetric and positive-definite (SPD). To verify the efficacy of the developed methodologies, the resulting solvers will be applied to fluid-structure interaction problems and nearly singular SPD problems.

这个项目的一个主要目标是创建一个框架，用于开发更健壮和用户友好的线性方程组解算器，线性方程组在科学、工程和工业应用中普遍存在。研究人员将对几何多重网格法和代数多重网格法进行综合分析和开发。几何多重网格(GMG)方法形成了一类多层求解器，用于求解由某些离散化的偏微分方程组(PDE)产生的线性方程组。代数多重网格(AMG)方法也是多层求解器，尽管这些技术避免了对关于底层网格几何或PDE的信息的任何依赖。因此，GMG方法是求解更受限制的一类线性系统的有效工具，其性能具有强大的理论支持，而AMG求解器适用于更一般的线性系统，尽管在证明其性能方面不具有相同的数学严谨性。这项研究项目将使用功能分析作为一个自然的框架，在统一的环境下研究GMG和AMG方法。由此产生的理论将为分析和开发健壮、高效和可伸缩的多级解算器建立强有力的指导原则。正在开发的迭代求解器将在开放源码并行代码中实现，供更广泛的科学计算社区使用，为模拟提供强大的工具，并为未来的算法研究和开发奠定基础。此外，该项目为博士生提供了参加各种教育和研究活动的机会，在这些活动中，他们将接受高级培训，参加会议，并与来自工业和能源部实验室的研究人员合作。该研究项目研究了在函数分析环境下分析GMG和AMG方法的统一框架。该框架为理解这些多层解算器中涉及的运算符、空间之间的关系和其他核心要素，例如粗略空间及其各自的基的构造，以及适用于各种现有AMG方法的收敛分析提供了坚实的基础。此外，对于离散化的偏微分方程组的问题，可以无缝地集成几何信息来构造辅助的基于网格的预条件算子和每一层上的高效光滑器，从而允许更灵活和积极的代数粗化。合并几何信息的更多好处在并行实现的近乎最佳的负载平衡和可预测的通信模式中实现。对于更一般的线性系统，该项目研究了使用(松弛的)压缩传感技术来保持粗空间算子的稀疏性，这些算子可以补充来自底层几何网格或矩阵的邻接图的信息，以获得对计算复杂性的控制。这些技术有望在解决非均匀网格问题或非对称正定矩阵问题中发挥作用。为了验证所开发方法的有效性，所得到的解算器将被应用于流固耦合问题和几乎奇异的SPD问题。

项目成果

Randomized and fault-tolerant method of subspace corrections

• DOI: 10.1007/s40687-019-0187-z
• 发表时间: 2019-08
• 期刊: Research in the Mathematical Sciences
• 影响因子: 1.2
• 作者: Xiaozhe Hu;Jinchao Xu;L. Zikatanov