naginterfaces.library.sum.fast_​gauss

naginterfaces.library.sum.fast_gauss(srcs, trgs, q, p1, p2, k, hin, tol)

fast_gauss calculates the multidimensional fast Gauss transform.

For full information please refer to the NAG Library document for c06sa

https://support.nag.com/numeric/nl/nagdoc_30/flhtml/c06/c06saf.html

Parameters

srcsfloat, array-like, shape $(d,n)$

$x$, the locations of the Gaussian sources.

trgsfloat, array-like, shape $(d,m)$

$y$, the locations of the target points at which the FGT will be evaluated.

qfloat, array-like, shape $\left(n\right)$

$q$, the weights of the Gaussian sources.

p1int

$p_1$, the number of terms of the first Taylor series to be evaluated.

p2int

$p_2$, the number of terms of the second Taylor series to be evaluated.

kint

$k$, the number of clusters into which the source points will be aggregated.

hinfloat, array-like, shape $\left(\text{lhin}\right)$

$h$, the standard deviations of the Gaussian sources. If $\text{lhin}<n$, the array will be expanded automatically by repeating $hin$ until it is of length $\text{n}$. See the G01 Introduction for further information.

tolfloat

$ϵ$, the desired accuracy of the FGT approximation of the DGT. Determines the radius of the source clusters: the contribution of a source point to the FGT approximation at a target point is disregarded if the source is outside the corresponding cluster radius.

Returns

p1int

$p1$ is unchanged.

p2int

$p2$ is unchanged.

kint

$k$ is unchanged.

vfloat, ndarray, shape $\left(m\right)$

$\hat{G}\left(y\right)$, the value of the FGT evaluated at $y$.

termfloat, ndarray, shape $\left(m\right)$

$term[j-1]$ contains the absolute value of the final Taylor series term that is largest, relative to the size of the sum of the corresponding series, across all clusters that contribute to the FGT at target point $v[j-1]$.

Raises

NagValueError

(errno $1$)

On entry, $d=⟨value⟩$.

Constraint: $d>0$.

(errno $2$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $3$)

On entry, $m=⟨value⟩$.

Constraint: $m>0$.

(errno $4$)

On entry, $p1=⟨value⟩$.

Constraint: $p1>0$.

(errno $5$)

On entry, $p2=⟨value⟩$.

Constraint: $p2>0$.

(errno $6$)

On entry, $k=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $1\le k\le n$.

(errno $7$)

On entry, $hin[⟨value⟩]=⟨value⟩$.

Constraint: $hin\left[\text{i}\right]>0.0$, for $\text{i}=0,\dots ,\text{lhin}-1$.

(errno $8$)

On entry, $\text{lhin}=⟨value⟩$.

Constraint: $1\le \text{lhin}\le n$.

(errno $9$)

On entry, $tol=⟨value⟩$.

Constraint: $tol>0.0$.

Warns

NagAlgorithmicWarning

(errno $10$)

On exit, $p1=⟨value⟩$, $p2=⟨value⟩$ and $k=⟨value⟩$.

$p1$, $p2$ or $k$ may have been too small to calculate $v[m-1]$ to the required accuracy $tol$.

Notes

fast_gauss calculates the $d$-dimensional fast Gauss transform (FGT), $\hat{G}\left(y\right)$, that approximates the discrete Gauss transform (DGT), $G\left(y\right)$, evaluated at a set of target points $y_{\text{j}}$, for $\text{j}=1,2,\dots ,m\in R^d$. The DGT is defined as:

$$G\left(y_j\right)=\sum _{i=1}^n{q}_i{e}^{-{\Vert y_j-x_i\Vert }_2^2/h_i^2}\text{,}j=1,\dots ,m$$

where $x_{\text{i}}$, for $\text{i}=1,2,\dots ,n\in R^d$, are the Gaussian source points, $q_{\text{i}}$, for $\text{i}=1,2,\dots ,n\in R^{+}$, are the source weights and $h_{\text{i}}$, for $\text{i}=1,2,\dots ,n\in R^{+}$, are the source standard deviations (alternatively source scales or source bandwidths).

This function implements the improved FGT algorithm presented in Raykar and Duraiswami (2005). The algorithm clusters the sources into $k$ distinct clusters and then computes two Taylor series approximations per cluster with $p_1$ and $p_2$ terms respectively. You must provide $p_1$, $p_2$ and $k$ when calling the function. See Accuracy below for a further discussion on accuracy when choosing their values.

The input array $hin$ of this function is designed to allow maximum flexibility in the supply of the standard deviation arguments by reusing, in a cyclic manner, elements of the array when it is less than $n$ elements long. For example, if all Gaussian sources have the same standard deviation then it is only necessary to set $\text{lhin}$ to $1$ and to provide the value of the standard deviation in $hin\left[0\right]$; the function will then automatically expand $hin$ to be of length $n$. For further details please see the G01 Introduction.

References

Greengard, L and Strain, J, 1991, The Fast Gauss Transform, SIAM J. Sci. Statist. Comput. (12(1)), 79–94

Raykar, V C and Duraiswami, R, 2005, Improved Fast Gauss Transform With Variable Source Scales, University of Maryland Technical Report CS-TR-4727/UMIACS-TR-2005-34