Advances in robust multilevel preconditioning methods for sparse linear systems

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

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.