one hand we may expand the shifted series as follows:

∞ ∞ ∞

(p)

f (t + 1) ≈ (p) (p)

cn Nn (t + 1) = cn Nn’1 (t) = cn+1 Nn (t),

n=’∞ n=’∞ n=’∞

(19.79)

but, on the other hand:

f (t + 1) = zf (t). (19.80)

Therefore there is a relation between coe¬cients:

cn+1 = zcn . (19.81)

Denoting c0 by c, it follows that

cn = z n c, (19.82)

and

∞

f (t) ≈ c z n Nn (t).

(p)

(19.83)

n=’∞

The in¬nite sum takes care of the periodicity. The constant c follows from

the requirement that the approximation is exact at the nodes t = k, k ∈ Z:

∞

k

z n Nn (k).

(p)

z =c (19.84)

n=’∞

This can be transformed by replacing n ’ k by n and shifting to the spline

function N = N0 , yielding

’1

p’1

z ’n N (p) (n)

c= . (19.85)

n=1

Thus in (19.83) and (19.85) we have obtained the solution for an interpolat-

ing exponential spline.

These exponential splines are particularly useful to approximate terms in a

554 Splines for everything

imag

1

t

t 2 0 real

012 K

p=4

exp(0.5πit)

3

(a) (b)

Figure 19.11 (a) the t-axis discretized in K = 16 intervals of unit length for use in

FFT. The function to be transformed is periodic on [0, K). The supports of the four

fourth-order interpolating spline functions, needed to approximate exp(2πimt/K),

is indicated by four lines. (b) Fourth-order spline interpolation (drawn curve) for

exp(0.5πit) (dashed circle).

Fourier sum, such as exp(iωt) (for arbitrary t), when fast Fourier transforms

(FFT) are used, de¬ned only at discrete values of ω and t. Take for example

a periodic t-axis divided into K (K is an even integer) intervals of unit

length. In FFT (see page 324) the angular frequencies are discretized in K

steps

2πm K K K

; m = ’ , ’ + 1, . . . , ’ 1,

ωm = (19.86)

K 2 2 2

and therefore one needs to evaluate exp(2πimt/K) for |m| ¤ K/2. Only

the values t = n, n = 0, . . . K ’ 1 can be handled by the FFT, and thus

one wishes to express exp(2πimt/K) in an interpolating spline series with

known values at integer values of t. This is accomplished by (19.83) and

(19.85):

∞

2πim 2πimn

≈c (p)

exp t exp Nn (t), (19.87)

K K

n=’∞

’1

p’1

2πimn

exp ’ N (p) (n)

c= . (19.88)

K

n=1

Figure 19.11(a) shows the t axis for the example K = 16 and the supports

for the four 4-th order spline functions needed for the indicated value of t.

The quantity to be Fourier transformed is thus distributed over the four pre-

ceding integer values. In Fig. 19.11(b) the fourth-order spline approximation

(drawn curve) of the function exp(0.5πit) (providing four points per period)

19.7 B-splines 555

is compared with the exact function (dashed circle) to show the accuracy of

the interpolation (better than 0.03).

The absolute error in the approximation equals approximately (|ω|/π)p

(Schoenberg, 1973; Silliman, 1974). This makes the approximation quite

imprecise for the highest frequency ωmax = π (m = K/2) that occurs in

the FFT. In fact, for the highest frequency the exponential exp(iπn) is

alternating between +1 and ’1, and the resulting spline is fully real. A

fourth-order spline does reproduce the real part cos πt of exp(πt) fairly well

(within 0.02) but fails completely to reproduce the imaginary part. For odd

values of the spline order p there is no solution since the sum evaluates to

0/0 (e.g., for p = 5 the sum would be 2/24 ’ 22/24 + 22/24 ’ 2/24 = 0).

This combination of values must be excluded. In usual applications the grid

is chosen su¬ciently ¬ne for the highest frequency terms to be of vanishing

importance.

References

Abraham, F. F. (2003). How fast can cracks move? A research adventure in mate-

rials failure using millions of atoms and big computers. Adv. Phys., 52, 727“90.

Abraham, F. F., Walkup, R., Gao. H. et al. (2002). Simulating materials failure by

using up to one billion atoms and the world™s fastest computer: work-hardening.

Proc. Natl. Acad. Sci., 99, 5783“7.

Abramowitz, M. and Stegun, I. A. (1965). Handbook of Mathematical Functions. New

York, Dover Publ.

Adelman, S. A. and Doll, J. D. (1974). Generalized Langevin equation approach

for atom/solid-surface scattering: Collinear atom/atomic chain model. J. Chem.

Phys., 61, 4242“5.

Ahlstr¨m, P., Wallqvist, A., Engstr¨m, S. and J¨nsson, B. (1989). A molecular dy-

o o o

namics study of polarizable water. Mol. Phys., 68, 563“81.

Allen, M. P. and Tildesley, D. J. (1987). Computer Simulation of Liquids. Oxford,

Clarendon Press.

Altman, S. L. (1986). Rotations, Quaternions and Double Groups. Oxford, Clarendon

Press.

Amadei, A., Linssen, A. B. M. and Berendsen, H. J. C. (1993). Essential dynamics of

proteins. Proteins, 17, 412“25.

Amadei,A., Chillemi, G., Ceruso, M., Grottesi, A. and Di Nola, A. (2000). Molecular

dynamics simulations with constrained roto-translational motions: theoretical basis

and statistical mechanical consistency. J. Chem. Phys., 112, 9“23.

Andersen, H. C. (1980). Molecular dynamics simulations at constant pressure and/or

temperature. J. Chem. Phys., 72, 2384“93.

Andersen, H. C. (1983). Rattle: a “velocity” version of the Shake algorithm for

molecular dynamics calculations. J. Comput. Phys., 52, 24“34.

Anderson, J. B. (1975). A random-walk simulation of the Schr¨dinger equation: H+ .

o 3

J. Chem. Phys., 63, 1499“1503.

Anderson, J. B. (1976). Quantum chemistry by random walk: H 2 P, H+ D3h 1 A1 ,

3

H2 3 Σ+ , H4 1 Σ+ , Be 1 S. J. Chem. Phys., 65, 4121“7.

u g