论文标题
通过随机基质矢量乘法分解蝴蝶分解
Butterfly factorization via randomized matrix-vector multiplications
论文作者
论文摘要
本文提出了一种自适应随机算法，用于计算$ m \ times n $矩阵的蝴蝶分解，规定$ m \ of of y n $，规定矩阵及其转换都可以迅速应用于任意向量。由此产生的分解由$ O（\ log n）$稀疏因子组成，每个因素都包含$ O（n）$ nonZero条目。可以使用$ o（n^{3/2} \ log n）$计算和$ o（n \ log n）$内存资源来实现分解。所提出的算法适用于具有严格误差绑定的表面积分方程求解器产生的强和弱的可接受性条件的矩阵，并并行实现。
This paper presents an adaptive randomized algorithm for computing the butterfly factorization of a $m\times n$ matrix with $m\approx n$ provided that both the matrix and its transpose can be rapidly applied to arbitrary vectors. The resulting factorization is composed of $O(\log n)$ sparse factors, each containing $O(n)$ nonzero entries. The factorization can be attained using $O(n^{3/2}\log n)$ computation and $O(n\log n)$ memory resources. The proposed algorithm applies to matrices with strong and weak admissibility conditions arising from surface integral equation solvers with a rigorous error bound, and is implemented in parallel.
