SC is the International Conference for
 High Performnance Computing, Networking, Storage and Analysis

SCHEDULE: NOV 13-19, 2010

Parallel Fast Gauss Transform

SESSION: Math Library Parallelization

EVENT TYPE: Paper, Best Paper (BP) Finalist

TIME: 11:00AM - 11:30AM


AUTHOR(S):Rahul S. Sampath, Hari Sundar, Shravan K. Veerapaneni


We present fast adaptive parallel algorithms to compute the sum of N Gaussians at N points. Direct sequential computation of this sum would take O(N2) time. The parallel time complexity estimates for our algorithms are O(N/np) for uniform point distributions and O( (N/np) log (N/np) + nplog np ) for non-uniform distributions using np CPUs. We incorporate a plane-wave representation of the Gaussian kernel which permits "diagonal translation". We use parallel octrees and a new scheme for translating the plane-waves to efficiently handle non-uniform distributions. Computing the transform to six-digit accuracy at 120 billion points took approximately 140 seconds using 4096 cores on the Jaguar supercomputer. Our implementation is "kernel-independent" and can handle other "Gaussian-type" kernels even when explicit analytic expression for the kernel is not known. These algorithms form a new class of core computational machinery for solving parabolic PDEs on massively parallel architectures.

Chair/Author Details:

Osni Marques (Chair) - Lawrence Berkeley National Laboratory

Rahul S. Sampath - Oak Ridge National Laboratory

Hari Sundar - Siemens

Shravan K. Veerapaneni - New York University

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar

The full paper can be found in the ACM Digital Library and IEEE Computer Society

   Sponsors    IEEE    ACM