.png){kind=icon}
.png){kind=icon}
Return
INTERPOLATIVE DECOMPOSITION BUTTERFLY
.png){kind=icon}
OA
AI
DOI：10.1137/19M1294873.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper introduces a kernel-independent interpolative decomposition butterfly factorization (IDBF) as a data-sparse approximation for matrices that satisfy a complementary low-rank property. The IDBF can be constructed in O(N logN) operations for an N x N matrix via hierarchical interpolative decompositions (IDs) if matrix entries can be sampled individually and each sample takes O(1) operations. The resulting factorization is a product of O(logN) sparse matrices, each with O(N) nonzero entries. Hence, it can be applied to a vector rapidly in O(N logN) operations. IDBF is a general framework for nearly optimal fast matrix-vector multiplication (matvec), which is useful in a wide range of applications, e.g., special function transformation, Fourier integral operators, and high-frequency wave computation. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms.
Keywords:
data-sparse matrix
butterfly factorization
interpolative decomposition
operator compression
Fourier integral operators
high-frequency integral equation
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W
