ALGORITHMS: Parallel Large-Scale Sparse Linear System Solvers: New Methods and Paradigms

研究人员开发了一套用于求解分布式稀疏线性方程组的并行代数多级技术，从而产生了用于在并行计算机上求解稀疏线性方程组的可移植的通用库--并行代数递归多层解算器(PARMS)。它们的目标之一是开始解决“特殊目的”和“一般目的”方法之间的“效率差距”。在现有解算器的一个极端上，稀疏直接法是健壮的、通用的，但价格昂贵。另一个极端是特殊目的的方法，如多重网格，它利用关于潜在问题的信息来量身定做某些解决方案的程序。这种方法可以是最优的，但它们的目标是解决原始的物理问题，而不是产生的线性系统。介于这两个极端之间的是预条件Krylov方法，其性能是可变的。这项研究的特点是对并行迭代求解器库应该提供什么的不同看法。研究人员强烈认为，需要一种新的范式，其中求解器不再是包含一组预条件条件的单一盒子，而是允许用户输入特定信息，甚至是求解算法的一部分，以便定制多级求解程序。这种方法是由PARMS的模块化设计实现的，与工业中使用的标准方法完全一致。这项研究中设想的新范式和方法还将包括在典型的解决过程中出现的一些其他关键问题。因此，在求解非线性方程组时，利用潜在的上下文是很重要的。同样重要的是，确保Parms代码为高效的稀疏直接求解器提供后备选项，以应对迭代求解器失败的情况。研究人员还计划探索随着计算网格的出现而开始出现的新问题。最后，他们将牢记解决方案算法的体系结构和问题相关的调整。调查人员开发的软件将继续公开提供。这两位研究人员都在重要的应用领域与研究人员进行了重大互动。PARMS-X代码也可能对研究生教育产生影响，就像SPARSKIT过去的情况一样。

The investigators have developed a set of parallel algebraic multilevel techniques for solving distributed sparse linear systems of equations, leading to the ``parallel Algebraic Recursive Multilevel Solver'' (pARMS), a portable and general purpose library for solving sparse linear systems on parallel computers. One of their goals is to begin to address the `efficiency gap' between `special purpose' and `general purpose' methods. On one extreme of the spectrum of solvers available, lie sparse direct methods which are robust, general-purpose, but expensive. On the other extreme, are special purpose methods, such as multigrid, which utilize information about the underlying problem to tailor-design certain solution procedures. Such methods can be optimal but they aim at solving the original physical problem instead of the resulting linear system. In between these extremes are the preconditioned Krylov methods whose performance is variable.This research is characterized by a different vision of what a library of parallel iterative solvers should offer. The investigators strongly believe that a new paradigm is required where a solver is no longer a monolithic box comprising a set of preconditioners, but allows the user to input specific information, indeed even parts of the solution algorithm, in order to tailor the multilevel solution procedure. This approach, which is enabled by the modular design of pARMS, is in perfect agreement with the standard approach used in industry. The new paradigms and methods envisioned in this research will alsoinclude a number of other key issues which arise in a typical solution process. Thus, it is important to exploit the underlying context when solving nonlinear systems of equations. It is also important to ensure that the pARMS code provides a fall-back option to an efficient sparse direct solver for situations where the iterative solver fails. The investigators also plan to explore new questions which are starting to emerge with the advent of the Computational Grid. Finally, they will keep in mind architecture- and problem-dependent tuning of solution algorithms.The software developed by the investigators will continue to be made publicly available. Both investigators have major interactions with researchers in important applications areas. The pARMS-X code is also likely to have an impact on graduate education, as was the case with SPARSKIT in the past.