BUTTERFLY FACTORIZATION VIA RANDOMIZED MATRIX-VECTOR MULTIPLICATIONS

Yang Liu

doi:10.1137/20M1315853

BUTTERFLY FACTORIZATION VIA RANDOMIZED MATRIX-VECTOR MULTIPLICATIONS

2021-03-09

10

OA

AI

DOI：10.1137/20M1315853

Original

Original request for help

Save

Abstract

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.

Keywords:

butterfly

randomized algorithm

matvec

direct solver

fast algorithm

numerical linear algebra

BUTTERFLY FACTORIZATION VIA RANDOMIZED MATRIX-VECTOR MULTIPLICATIONS

Abstract

Journal

Organization