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方法的融合分析。此外，对于源自离散PDE的问题，在每个级别上构建基于辅助网格的预处理和高效的Smoothorth的几何信息的整合可以无缝集成，从而使更灵活，更具侵略性的代数块状。合并几何信息的更多好处是在几乎最佳的负载平衡和可预测的沟通模式中实现的，用于并行实现。对于更通用的线性系统，该项目研究了（放松的）压缩感测技术来保留粗大空间操作员的稀疏性，可以从基础几何网格或矩阵的邻接图中补充信息，以获得对计算复杂性的控制。可以预期，这些技术将有助于解决非对称和非对称和正定石的矩阵（SPD）的矩阵问题的问题。为了验证开发方法的疗效，所得的求解器将应用于流体结构的相互作用问题和几乎奇异的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