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.