We present a fast direct solver for boundary integral equations on complex surfaces in three dimensions using an extension of the recently introduced strong recursive skeletonization scheme. For problems that are not highly oscillatory, our algorithm computes an ${LU}$-like hierarchical factorization of the dense system matrix, permitting application of the inverse in $O(N)$ time, where $N$ is the number of unknowns on the surface. The factorization itself also scales linearly with the system size, albeit with a somewhat larger constant. The scheme is built on a level-restricted adaptive octree data structure, and therefore it is compatible with highly nonuniform discretizations. Furthermore, the scheme is coupled with high-order accurate locally-corrected Nystrom quadrature methods to integrate the singular and weakly-singular Green's functions used in the integral representations. Our method has immediate applications to a variety of problems in computational physics. We concentrate here on studying its performance in acoustic scattering (governed by the Helmholtz equation) at low to moderate frequencies.
翻译:我们利用最近推出的强大循环骨质化计划的延伸,为复杂表面三个维度的边界整体方程式展示了一个快速直接求解器。对于不高度混凝土的问题,我们的算法对密集系统矩阵计算了一个类似于${LU}的等级因子化,允许在美元(N)美元的时间里应用反向的数值,即表面的未知数为$(N)美元。因子化本身也以系统大小为线性尺度,尽管系统大小有较大的恒定值。这个计划是建立在一个受层次限制的适应性奥氏树数据结构上,因此与高度不统一的离散性兼容。此外,这个计划与高顺序的精确本地校正的Nystrom 矩形法相结合,将单项和弱项格林函数纳入整体表达中。我们的方法直接应用于计算物理学的多种问题。我们在这里集中研究其低至中频频率的声波散(由Helmholtz方程式导导出)的性。