2013/05/20 by Jack Poulson, Poulson, Jack, Laurent Demanet +5 · 1 citation
Computer Science · Mathematics · #FOS: Mathematics #Numerical Analysis (math.NA) #cs.NA #math.NA
paper · pdf · doi:10.48550/arxiv.1305.4650
To appear in SIAM Journal on Scientific Computing
arxiv created 2013/11/25 · arxiv updated 2013/11/26
The butterfly algorithm is a fast algorithm which approximately evaluates a discrete analogue of the integral transform ∫ 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(Nd) 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(r2 Nd log N). A parallelization of the butterfly algorithm is introduced which, assuming a message latency of αand per-process inverse bandwidth of β, executes in at most O(r2 Nd/p log N + βr Nd/p + α)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 Φ(x,y)), where Φ(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 3D 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.