论文标题
高频波方程的蝴蝶压缩的稀疏近似多峰分解
Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations
论文作者
论文摘要
我们提供了一个快速而近似的多频求解器，用于由有限差分，有限数量或高频波方程的有限元元素离散化引起的大规模稀疏线性系统。所提出的求解器利用蝴蝶算法及其层次矩阵扩展，通过图指导的进入评估或基于随机的矩阵 - 矢量乘数方案来压缩和分解大型额叶矩阵。复杂性分析和数值实验证明了$ \ MATHCAL {O}（N \ log^2 N）$计算和$ \ MathCal {O}（N）$内存复杂性，将内存复杂性应用于$ N \ times n $稀疏系统，该系统由3D高频Helmholtz和Maxwell问题产生。
We present a fast and approximate multifrontal solver for large-scale sparse linear systems arising from finite-difference, finite-volume or finite-element discretization of high-frequency wave equations. The proposed solver leverages the butterfly algorithm and its hierarchical matrix extension for compressing and factorizing large frontal matrices via graph-distance guided entry evaluation or randomized matrix-vector multiplication-based schemes. Complexity analysis and numerical experiments demonstrate $\mathcal{O}(N\log^2 N)$ computation and $\mathcal{O}(N)$ memory complexity when applied to an $N\times N$ sparse system arising from 3D high-frequency Helmholtz and Maxwell problems.
