Collaborative Research: Super-fast Direct Sparse Solvers

协作研究：超快速直接稀疏求解器

• 批准号: 0515320
• 负责人: Shivkumar Chandrasekaran
• 金额: $ 17.5万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-01 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0515320&HistoricalAwards=false
• 关键词: Collaborative; Research; Super; fast; Direct

ABSTRACT0515320Shivkumar ChandrasekaranU of California - SBCollaborative Research: Super-fast direct sparse solversThe numerical solution of partial differential equations (PDE) is a key enabling technology in alldisciplines of engineering and science. Nevertheless the numerical solution of three-dimensionalPDEs is a critical bottle-neck that prevents this potential from being realized. This proposaladvances techniques that can be used to overcome this bottle-neck. Discretized elliptic PDEs are normally solved by iterative schemes since the fill-in during sparse Gaussian elimination is excessive. This proposal observes that the fill-in, in a certain ordering, has low numerical rank in the off-diagonal blocks, and that this structure can be computed and exploited to construct direct solvers that are linear in the number of unknowns. The outcome of the proposed research has the potential to create a novel class of pre-conditioners that in conjunction with iterative solvers can become powerful weapons for solving difficult elliptic PDEs.The intellectual merit of the proposal stems from the complicated structure in the fill-in thatmust be first inferred from regularity results for Green's functions in elliptic PDE theory and thenconverted into effective linear-time algorithms to both capture the structure on the fly during sparseGaussian elimination, and then exploited to speed up the very same Gaussian elimination. The impact of the proposal will be to provide new solvers for difficult PDEs. In particular thesoftware that is developed will be made available to the community, and should enable scientists and engineers to have a new tool for their difficult problems. It will also infuse fresh ideas into the field of sparse direct solvers and unify it with the field of iterative methods.

加州大学伯克利分校的Shivkumar ChandraseKaranU合作研究：超快直接稀疏求解偏微分方程(PDE)的数值解是工程和科学所有学科的关键使能技术。然而，三维偏微分方程组的数值解是阻碍这一潜力实现的关键瓶颈。这一提议提出了可以用来克服这一瓶颈的技术。离散的椭圆型偏微分方程组由于稀疏高斯消去法中的填充量过大，通常采用迭代格式求解。这项建议观察到，在某种顺序中，填充在非对角线块中具有较低的数值排名，并且可以计算和利用这种结构来构造在未知数数量中线性的直接求解器。提出的研究结果有可能创建一类新的预条件，与迭代求解器相结合可以成为求解困难的椭圆偏微分方程组的有力武器。该方案的智能优点来自于填充中的复杂结构，必须首先从椭圆偏微分方程理论中格林函数的正则性结果推导出该结构，然后转换为有效的线性时间算法，以便在稀疏高斯消去过程中动态捕捉结构，然后利用该算法来加速完全相同的高斯消元。该提案的影响将是为困难的PDE提供新的解算器。特别是，开发的软件将向社区提供，并应使科学家和工程师有一个新的工具来解决他们的难题。它还将为稀疏直接求解器领域注入新的思想，并将其与迭代方法领域统一起来。