Advances in robust multilevel preconditioning methods for sparse linear systems

这个项目的主要目标是研究解线性方程组的多层预适应技术，高度重视稳健性问题。这些方法中使用的关键概念之一是粗化，即将系统的一组变量(称为“精细”未知数)缩减为一个较小的集合(称为“粗略”未知数)的方法，从而产生精细集合的良好表示。到目前为止，粗化主要是从代数多重网格的角度来考察的。一些多层次ILU类型的技术，主要基于粗化思想，将被研究。研究小组还将研究区域分解类型方法中的一组新的多级低阶近似技术。许多因素使得这些方法非常有吸引力，包括它们的健壮性和它们在高性能计算机上的潜在有效性，例如使用GPGPU的计算机。最后，为了将预处理器的开发与应用更紧密地联系在一起，研究小组将考虑开发可称为“针对应用程序量身定做的预条件器”的方法。尽管在过去20年中，在用迭代方法求解大型稀疏线性方程组方面取得了巨大的进展，但这些方法的最新水平在许多领域仍然不令人满意。其中最重要的是迭代技术在处理各种实际问题时缺乏健壮性。最近对预条件Krylov子空间方法(PKSM)的研究旨在通过融合不同层次的技术来实现通用性和效率之间的良好折衷，包括提高可伸缩性的多级概念和吸收直接求解方法的思想来提高鲁棒性。在部署这些改进的同时，对迭代解决方案方法的开发人员的需求也在发生变化。应用程序变得更具挑战性，新的计算环境正在制造过时的复杂软件，这些软件往往需要几年时间才能成熟。这项研究提案的目的是解决近年来PKSM面临的新挑战和新问题，并探讨进展至关重要的更常见的研究问题。所有将在该项目下开发的通用代码将在GNU公共使用许可证下免费分发。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.