Collaborative Research: Super-fast Direct Sparse Solvers

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

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.