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.

该项目的主要目的是研究用于求解方程式线性系统的多层次预处理技术，并高度重视鲁棒性问题。这些方法中使用的关键概念之一是将系统（称为“ Fine”未知数称为“ Fine”未知数）减少的方法（称为``粗''未知数），从而使罚款集的良好表示。到目前为止，已经大部分从代数多网格的角度看待了变形。将研究许多主要基于粗糙思想的多层ILU类型技术。研究团队还将研究域分解类型方法中一组新的多级低级近似技术。许多因素使这些方法非常吸引人，包括它们的鲁棒性以及它们对高性能计算机的潜在有效性，例如使用GPGPU的计算机。最后，为了将预科人员更加紧密地与应用联系起来，研究团队将考虑开发可能称为“应用程序销售的预先调查器”的方法。尽管在过去的二十年中，在过去的二十年中取得了巨大的进步，在大型稀疏方程式解决方程式的解决方案解决方案解决方程式系统中，这些方法是通过迭代的方法，这些方法的状态不可分割的领域仍然不可能。其中最重要的是在处理各种现实生活问题时缺乏迭代技术的鲁棒性。关于预处理的Krylov子空间方法（PKSM）的最新研究旨在通过合并来自不同视野的技术，包括多层次的概念，以提高直接解决方案方法来提高鲁棒性，从而实现一般性和效率之间的良好妥协。在部署这些改进的同时，对迭代解决方案方法开发人员的需求正在发生变化。应用程序变得更具挑战性，新的计算环境正在制造过时的复杂软件，通常花费数年的时间才能成熟。这项研究建议的目的是解决近年来PKSM出现的新挑战和问题，以及探索进步至关重要的更常见的研究问题。根据GNU公共使用许可，将根据该项目开发的所有常规使用代码将自由分发。 PI已经以这种方式进行了长期的练习，以这种方式分发代码。该项目将影响对学术界，工业和政府实验室需求至关重要的领域研究生的培训。在计算数学方面对专家的需求大幅增长的时候，在这个广泛领域培训的研究生人数减少了。 PI将在吸引和培训与科学计算和高性能计算有关的主题的学生方面做出重大努力。由于在学生职业生涯的早期阶段将兴趣引发到这些领域很重要，因此该提案强调了计划在整个期限内雇用两名本科暑期实习生来研究该建议的特定主题。在其他培训活动中，PI将继续进行自由传播书籍，讲座和MATLAB脚本的实践，以进行教育。