Collaborative Research: Super-fast Direct Sparse Solvers

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

ABSTRACT051034Ming GuU of California - BerkeleyCollaborative Research: Super-fast direct sparse solversThe numerical solution of partial differential equations (PDE) is a key enabling technology in all disciplines of engineering and science. Nevertheless the numerical solution of three-dimensional PDEs is a critical bottle-neck that prevents this potential from being realized. This proposal advances 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 that must be first inferred from regularity results for Green's functions in elliptic PDE theory and then converted into effective linear-time algorithms to both capture the structure on the fly during sparse Gaussian 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.