Show simple item record

Improved Fast Gauss Transform

dc.contributor.authorYang, Changjiangen_US
dc.contributor.authorDuraiswami, Ramanien_US
dc.contributor.authorGumerov, Nail A.en_US
dc.description.abstractThe fast Gauss transform proposed by Greengard and Strain reduces the computational complexity of the evaluation of the sum of $N$ Gaussians at $M$ points in $d$ dimensions from $O(MN)$ to $O(M+N)$. However, the constant factor in $O(M+N)$ grows exponentially with increasing dimensionality $d$, which makes the algorithm impractical in higher dimensions. In this paper we present an improved fast Gauss transform where the constant factor is reduced to asymptotically polynomial order. The reduction is based on a new multivariate Taylor expansion scheme combined with the space subdivision using the $k$-center algorithm. The complexity analysis and error bound are presented which helps to determine parameters automatically given a desired precision to which the sum must be evaluated. We present numerical results on the performance of our algorithm and provide numerical verification of the corresponding error estimate. (UMIACS-TR-2003-64)en_US
dc.format.extent1085075 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4495en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-2003-64en_US
dc.titleImproved Fast Gauss Transformen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record