"AF:Small:Efficient and reliable low-rank approximation techniques and fast solutions to large sparse linear equations"

“AF：Small：高效可靠的低秩逼近技术和大型稀疏线性方程的快速解”

• 批准号: 1319312
• 负责人: Ming Gu
• 金额: $ 40万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319312&HistoricalAwards=false
• 关键词: AF; Small; Efficient; reliable; low

In many computational and engineering problems, it is critical to solve large sparse linear systems of equations rapidly and reliably. Nevertheless, many practical but difficult large linear systems of equations remain out of reach computationally. In this project, the PI develops structured fast direct methods and pre-conditioners for solving such large sparse linear systems. These methods systematically exploit potentially rich numerical low-rank patterns within the fill-ins for large reductions in computational time and memory. The efficiency of these methods comes from three innovative design strategies: the PI develops randomized algorithms that can rapidly compute high quality low-rank approximations with low numerical compression overhead; the PI adapts these methods to preserve desirable properties of the original matrix for enhanced numerical reliability; and the PI re-organizes the computations so that no numerical compression and data communication is performed unless necessary.The outcome of this research has the potential to create a novel class of direct solvers and pre-conditioners that in conjunction with iterative solvers can become powerful weapons for solving difficult large sparse linear systems, and the low-rank approximation schemes would become a valuable tool for the general scientific community, as effective data compression is essential in many areas of science and engineering. Mathematical software for rapidly solving large sparse linear systems of equations and for effective compression of large data sets will be made available to the scientific computing public.

在许多计算和工程问题中，快速可靠地求解大型稀疏线性方程组是至关重要的。然而，许多实用但困难的大型线性方程组仍然无法计算。在这个项目中，PI开发了结构化快速直接方法和预处理器来解决这种大型稀疏线性系统。这些方法系统地利用潜在的丰富的数值低秩模式内的填充大幅减少计算时间和内存。这些方法的效率来自于三个创新的设计策略：PI开发了随机算法，可以快速计算高质量的低秩近似，数值压缩开销低; PI采用这些方法来保持原始矩阵的期望属性，以增强数值可靠性;和PI重新-组织的计算，使没有数值压缩和数据通信是执行，除非必要的。这项研究的成果有可能创造一个一类新的直接求解器和预处理器，结合迭代求解器可以成为解决困难的大型稀疏线性系统的强大武器，低秩近似方案将成为一般科学界的宝贵工具，因为有效的数据压缩在许多科学和工程领域是必不可少的。将向科学计算公众提供用于快速求解大型稀疏线性方程组和有效压缩大型数据集的数学软件。