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.