BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20101116T170000Z
DTEND:20101116T173000Z
LOCATION:393
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: 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(N<sup>2</sup>) time.=0AThe parallel time complexity estimates for our algorithms are O(N/n<sub>p</sub>) for uniform point distributions and=0AO( (N/n<sub>p</sub>) log (N/n<sub>p</sub>) + n<sub>p</sub>log n<sub>p</sub> )=0Afor non-uniform distributions using n<sub>p</sub> 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.=0A=0AOur 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.
SUMMARY:Parallel Fast Gauss Transform
PRIORITY:3
END:VEVENT
END:VCALENDAR