sn

e’(t’s) =

2

h n (t)

n!

n=0

and the multivariate version gives

1±

e’

2

=

x’y

y h ± (x),

2

±!

±∈Nd

0

so that the stated identity follows by exchanging summations.

To derive the approximation error we ¬rst split the Hermite representation of e’(t’s) into

2

two terms:

∞

p

sn

s!

e’(t’s) =

2

h n (t) + h n (t) =: A p (t, s) + R p (t, s).

n! n!

n=0 n= p+1

√

Cramer™s inequality gives us a bound on each term for t ∈ R and |s| 2 ¤ r < 1:

√

p p

|s 2|n 1 ’ r p+1

|A p (t, s)| ¤ ¤ rn = ,

√

1’r

n!

n=0 n=0

√n

∞ ∞

1 1

|R p (t, s)| ¤ √ |s 2| ¤ √ p+1

rn

r

( p + 1)! n= p+1 ( p + 1)! n=0

r p+1

1

=√ .

( p + 1)! 1 ’ r

Since we have

d

’ x’y 2

= A p (x j , y j ) + R p (x j , y j )

e 2

j=1

15.1 Fast multipole methods 263

√

for arbitrary x, y ∈ Rd we can conclude for x ∈ Rd and ¤ r < 1 that

2y ∞

d

1±

e’ y h ± (x) = e’

2 2

’ ’ A p (x j , y j )

x’y x’y

2 2

±!

±¤ p j=1

d’k

d’1

r p+1

1 d

¤ (1 ’ r p+1 )k ,

√

(1 ’ r )d ( p + 1)!

k

k=0

which in turn establishes the stated estimate on s ’ s.

This ¬nishes our discussion of the far-¬eld expansion of the Gaussian around zero.

Shifting and scaling give us far-¬eld expansions around other centers and with different

stretch parameters.

Moreover, as mentioned before, we can use the far-¬eld expansion of the Gaussian and

the fast Gauss transform to derive far-¬eld expansions for most of the basis functions in

use. The key idea here is to exploit the fact that a radial function φ : [0, ∞) ’ R is often

(conditionally) positive de¬nite on every Rd . First, if φ is positive de¬nite on every Rd then

we know from the theory of completely monotone functions that it has a representation

∞

e’r t d±(t)

2

φ(r ) =

0

with a nonnegative Borel measure ±, which has a Lebesgue density in all relevant cases.

Hence, the radial sum becomes

∞N

N

c j e’

2

c j φ( x ’ x j 2) =

x’x j 2t d±(t)

0

j=1 j=1

and we can use a quadrature rule to boil this down to a ¬nite sum of far-¬eld expansions of

the Gaussians.

Second, if φ is conditionally positive de¬nite of order m > 0 then we have such a represen-

tation for the mth-order derivative of φ. Integrating this representation gives a representation

of φ itself. Let us explain this in more detail using two examples.

√

Proposition 15.7 The inverse multiquadric φinv (r ) = 1/ 1 + r 2 has the representation

∞

1

t ’1/2 e’r t e’t dt.

2

φinv (r ) = √

π 0

Hence, the associated radial sum can be written as

∞N

N

1

c j e’ t ’1/2 e’t dt.

2

c j φinv ( x ’ x j 2) = √

x’x j 2t

π 0

j=1 j=1

√

The multiquadric φmul (r ) = 1 + r 2 has the representation

∞

1

(1 ’ e’r t )t ’3/2 e’t dt.

2

φmul (r ) = 1 + √