Memory-Efficient Implementation of Sparse Linear Solvers

科学和工程中许多重要问题的解决依赖于有效地求解稀疏线性系统，即系数中有许多零项的方程组。这个项目将研究创建稀疏线性求解器的技术，以有效地利用单处理器计算机上的内存层次结构。它将专注于将原始系统重新表述为阻塞系统的方法，并仔细选择块以加快收敛。性能编程技术将降低分块版本所需的额外矩阵向量运算的成本。这项工作有三个技术目标。第一个是通过分析和实验，有助于理解内存效率高的稀疏线性求解器的数值行为。第二是确定至少一个健壮的、内存效率高的稀疏线性求解器，以包含在可移植可扩展科学计算工具包(PETSc)库中。最终目标是开发一个以内存为中心的性能指标，用于评估线性代数算法的内存流量需求。

Solving many important problems in science and engineering depends on efficiently solving sparse linear systems, that is, sets of equations with many zero entries in the coefficients. This project will study techniques for creating sparse linear solvers that make efficient use of the memory hierarcy on single processor computers. It will concentrate on methods that reformulate the original system as a blocked system, with careful choices of the blocks to speed up convergence. Performance programming techniques will reduce the costs of the extra matrix-vector operations needed by the blocked version.There are three technical goals of this work. The first is to contribute to the understanding of the numerical behavior of memory-efficient sparse linear solvers through analysis and experiment. The second is to identify at least one robust, memory-efficient sparse linear solver for inclusion in the Portable Extensible Toolkit for Scientific Computation (PETSc) library. The final goal is to develop a memory-centric performance metric for evaluating the memory traffic requirements of linear algebra algorithms.