.png){kind=icon}
返回
BUTTERFLY FACTORIZATION VIA RANDOMIZED MATRIX-VECTOR MULTIPLICATIONS
.png){kind=icon}
OA
AI
DOI：10.1137/20M1315853.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper presents an adaptive randomized algorithm for computing the butterfly factorization of an m x n matrix with m ti n provided that both the matrix and its transpose can be rapidly applied to arbitrary vectors. The resulting factorization is composed of O(logn) sparse factors, each containing O(n) nonzero entries. The factorization can be attained using O(n(3/2) logn) computation and O(n logn) memory resources. The proposed algorithm can be implemented in parallel and can apply to matrices with strong or weak admissibility conditions arising from surface integral equation solvers as well as multi-frontal-based finite-difference, finite-element, or finite-volume solvers. A distributed-memory parallel implementation of the algorithm demonstrates excellent scaling behavior.
Keyword:
butterfly
randomized algorithm
matvec
direct solver
fast algorithm
numerical linear algebra
期刊
IF:
2.6
论文数:
5.1K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容