התמרת גאוס מהירה ומקבילית

בפרסומי הכנס, סופר-קומפיוטינג 10 (מחשוב על), SC '10 Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis , שהתקיים השנה בניו אורלינס שבלואיזיאנה, בארה"ב, לכד את עיניי פרסום על התמרת גאוס מהירה ומקבילית. החוקרים מציגים אלגוריתם מקבילי לחישוב הסכום של N גאוסיאנים ב-N נקודות. בעוד שחישוב סדור של סכום זה דורש סיבוכיות זמן מסדר גודל ריבועי ב-N, האלגוריתם שהחוקרים מציגים דורש סיבוכיות זמן מקבילית שמוערכת בסדר גודל של- N/Np להתפלגות נקודות אחידה ולסיבוכיות זמן מקבילית שמוערכת בסדר גודל של N/np log N/np + nplognp עבור התפלגות נקודות שאינה אחידה. הקבוע Np מייצג את מספר המעבדים שבשימוש האלגוריתם.

הנה קישור למאמר והנה התקציר של המאמר:

Parallel Fast Gauss Transform
Authors: Rahul S. Sampath * Hari Sundar * Shravan K. Veerapaneni

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^2)$ time. The parallel time complexity estimates for our algorithms are $O(N/np)$ for uniform point distributions and $O(N/np log N/np + nplognp)$ for nonuniform distributions using np CPUs. We incorporate a planewave 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 nonuniform distributions. Computing the transform to six-digit accuracy at 120 billion points took approximately 140 seconds using 4096 cores on the Jaguar supercomputer at the Oak Ridge National Laboratory. Our implementation is kernel-independent and can handle other “Gaussian-type” kernels even when an 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.