Name
Abstract | ||
|---|---|---|
The butterfly algorithm is a fast algorithm which approximately evaluates a discrete analogue of the integral transform integral R-d K(x, y)g(y)dy at large numbers of target points when the kernel, K(x, y), is approximately low-rank when restricted to subdomains satisfying a certain simple geometric condition. In d dimensions with O(N-d) quasi-uniformly distributed source and target points, when each appropriate submatrix of K is approximately rank-r, the running time of the algorithm is at most O(r(2)N(d) logN). A parallelization of the butterfly algorithm is introduced which, assuming a message latency of alpha and per-process inverse bandwidth of beta, executes in at most O(r(2) N-d/p logN + (beta r N-d/p + alpha)log p) time using p processes. This parallel algorithm was then instantiated in the form of the open-source DistButterfly library for the special case where K(x, y) = exp(i Phi(x, y)), where Phi(x, y) is a black-box, sufficiently smooth, real-valued phase function. Experiments on Blue Gene/Q demonstrate impressive strong-scaling results for important classes of phase functions. Using quasi-uniform sources, hyperbolic Radon transforms, and an analogue of a three-dimensional generalized Radon transform were, respectively, observed to strong-scale from 1-node/16-cores up to 1024-nodes/16,384-cores with greater than 90% and 82% efficiency, respectively. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1137/130921544 | SIAM JOURNAL ON SCIENTIFIC COMPUTING |
Keywords | DocType | Volume |
butterfly algorithm,Egorov operator,Radon transform,parallel,Blue Gene/Q | Journal | 36 |
Issue | ISSN | Citations |
1 | 1064-8275 | 0 |
PageRank | References | Authors |
0.34 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jack Poulson | 1 | 138 | 8.85 |
| Laurent Demanet | 2 | 750 | 57.81 |
| Nicholas Maxwell | 3 | 6 | 0.88 |
| Lexing Ying | 4 | 1273 | 103.92 |