Advances in robust multilevel preconditioning methods for sparse linear systems

稀疏线性系统鲁棒多级预处理方法的进展

• 批准号: 1216366
• 负责人: Yousef Saad
• 金额: $ 30万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-15 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1216366&HistoricalAwards=false
• 关键词: Advances; robust; multilevel; preconditioning; methods

The primary goal of this project is to investigate multi-level preconditioning techniques for solving linear systems of equations, placing a high emphasis on robustness issues. One of the key concepts used in these methods is that of coarsening, i.e., the method of reducing a set of variables of a system (called `fine' unknowns) to a smaller set (called `coarse' unknowns) which yields a good representation of the fine set. So far, coarsening has been viewed mostly from the angle of algebraic multi-Grid. A number of multi-level ILU type techniques, primarily based on coarsening ideas, will be studied. The research team will also investigate a new set of Multi-Level Low-Rank approximation techniques within Domain-Decomposition type methods. A number of factors make these methods very appealing, including their robustness and their potential effectiveness on high-performance computers, e.g., ones employing GPGPUs. Finally, in an effort to tie the development of preconditioners more closely with applications, the research team will consider methodologies for developing what may be termed `application-tailored preconditioners.'Though enormous progress has been made in the last two decades in the solution of large sparse linear systems of equations by iterative methods, the state-of-the-art of these methods remains unsatisfactory in many areas. Foremost among these is the lack of robustness of iterative techniques in dealing with a variety of real-life problems. Recent research on Preconditioned Krylov Subspace Methods (PKSMs) has aimed at achieving a good compromise between generality and efficiency by incorporating techniques from different horizons, including multilevel concepts to improve scalability and adopting ideas from direct solution methods to improve robustness. At the same time that these improvements are being deployed, the demands on developers of iterative solution methods are changing. Applications have become much more challenging, and new computational environments are making obsolete complex software that often took several years to mature. The aim of this research proposal is to address new challenges and questions that have emerged for PKSMs in recent years as well as to explore more common research issues where progress is of vital importance. All general use codes that will be developed under this project will be freely distributed under the GNU public use license. The PI already has a long practice with distributing codes in this fashion. This project will have an impact on the training of graduate students in a field that is vital to the needs of academia, industry, and government laboratories. At a time where there is a significant upsurge of demand for specialists in computational mathematics, the number of graduate students trained in this broad area has diminished. The PI will place a major effort in attracting and training students in topics related to scientific computing and high-performance computing. Because it is important to sparkle the interest into these areas at an early stage of the student career, the proposal highlights plans for employing two undergraduate summer interns to work on specific topics of this proposal, throughout its duration. Among other training activities the PI will continue the practice of freely disseminating books, lecture notes, and MATLAB scripts for educational purposes.

该项目的主要目标是研究求解线性方程组的多级预处理技术，高度强调鲁棒性问题。这些方法中使用的关键概念之一是粗化，即将系统的一组变量（称为“精细”未知数）减少到一个较小的集合（称为“粗糙”未知数），从而产生精细集的良好表示。迄今为止，人们主要是从代数多网格的角度来看待粗化问题。一些主要基于粗化思想的多层次逻辑单元类型技术将被研究。研究小组还将在域分解类型方法中研究一套新的多级低秩近似技术。许多因素使这些方法非常吸引人，包括它们的健壮性和它们在高性能计算机上的潜在有效性，例如，使用gpgpu的计算机。最后，为了将预调节器的开发与应用更紧密地联系起来，研究团队将考虑开发所谓的“应用定制预调节器”的方法。虽然在过去的二十年中，用迭代方法求解大型稀疏线性方程组取得了巨大的进展，但这些方法的最新技术在许多领域仍然令人不满意。其中最重要的是迭代技术在处理各种现实问题时缺乏鲁棒性。最近对预条件Krylov子空间方法（PKSMs）的研究旨在通过结合不同领域的技术，包括多层概念来提高可扩展性和采用直接解方法的思想来提高鲁棒性，从而在通用性和效率之间取得良好的妥协。在部署这些改进的同时，迭代解决方案方法的开发人员的需求也在变化。应用程序变得更具挑战性，新的计算环境正在使那些通常需要几年时间才能成熟的复杂软件变得过时。本研究计划的目的是解决近年来PKSMs出现的新挑战和问题，以及探索更常见的研究问题，其中进展至关重要。所有在本项目下开发的通用代码将在GNU公共使用许可证下自由发布。PI在以这种方式分发代码方面已经有了很长的实践。这个项目将对研究生的培养产生影响，这对学术界、工业界和政府实验室的需求至关重要。在对计算数学专家的需求急剧上升的时候，在这一广泛领域受过培训的研究生人数却减少了。PI将在科学计算和高性能计算相关的主题上吸引和训练学生。因为在学生职业生涯的早期阶段激发对这些领域的兴趣是很重要的，所以该提案强调了在整个提案期间雇用两名本科生暑期实习生来研究该提案的具体主题的计划。在其他培训活动中，PI将继续为教育目的自由传播书籍、课堂讲稿和MATLAB脚本。