Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1137/19M1294873 | SIAM JOURNAL ON SCIENTIFIC COMPUTING |
Keywords | DocType | Volume |
data-sparse matrix,butterfly factorization,interpolative decomposition,operator compression,Fourier integral operators,high-frequency integral equation | Journal | 42 |
Issue | ISSN | Citations |
2 | 1064-8275 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qiyuan Pang | 1 | 0 | 0.34 |
| Kenneth L. Ho | 2 | 55 | 6.01 |
| Haizhao Yang | 3 | 46 | 13.03 |