1. Butterfly Factorization Via Randomized Matrix-Vector Multiplications
- Author
-
Yang Liu, Xiaoye S. Li, Pieter Ghysels, Eric Michielssen, Han Guo, and Xin Xing
- Subjects
FOS: Computer and information sciences ,math.NA ,Numerical & Computational Mathematics ,ComputerApplications_COMPUTERSINOTHERSYSTEMS ,Approx ,computer.software_genre ,randomized algorithm ,Combinatorics ,Matrix (mathematics) ,Factorization ,butterfly ,Transpose ,fast algorithm ,FOS: Mathematics ,numerical linear algebra ,matvec ,Mathematics - Numerical Analysis ,Computer Science::Databases ,cs.NA ,Mathematics ,Numerical linear algebra ,Numerical and Computational Mathematics ,Applied Mathematics ,Computation Theory and Mathematics ,Numerical Analysis (math.NA) ,Fast algorithm ,cs.MS ,Randomized algorithm ,direct solver ,Computational Mathematics ,Butterfly ,Computer Science - Mathematical Software ,Mathematical Software (cs.MS) ,computer - Abstract
This paper presents an adaptive randomized algorithm for computing the butterfly factorization of an m × 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(n3/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 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.
- Published
- 2021