1. BUTTERFLY FACTORIZATION VIA RANDOMIZED MATRIX-VECTOR MULTIPLICATIONS.
- Author
-
YANG LIU, XIN XING, HAN GUO, MICHIELSSEN, ERIC, GHYSELS, PIETER, and XIAOYE SHERRY LI
- Subjects
FACTORIZATION ,MULTIPLICATION ,PARALLEL algorithms ,BUTTERFLIES ,NUMERICAL solutions for linear algebra - Abstract
This paper presents an adaptive randomized algorithm for computing the butterfly factorization of an m x n matrix with m ≈ 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 can be implemented in parallel and can apply to matrices with strong or weak admissibilit y 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. [ABSTRACT FROM AUTHOR]- Published
- 2021
- Full Text
- View/download PDF