Computational Physics

8.8 Langevin dynamics simulation 247

whereKis the average size of the interaction list, which is at most 27.KandM
are fixed numbers, there areO(lnN)levels, so the total number of steps scales as
O(NlnN).
For two dimensions, the multipole moment expansion is very simple if the space
is viewed as a complex plane with particles at positionsz=x+iy. The potential
is then given as the real part of ln(z)and this can easily be expanded in a Taylor
expansion around the centre of the cell. For a cluster centred at the origin and
consisting of particles of chargeqiat positionszi, the potential at the pointzis
given by

U(z)=

∑Nc

i= 1

qiln(z−zi)=a 0 lnz−

∑M

k= 1

ak

zk

+O

(

R

z

)M+ 1

(8.139)

whereRis the linear size of the cluster containingNcparticles and the moment
expansion coefficientsakare given by

a 0 =

∑

i

qi and ak=

∑Nc

i= 1

qizik

k

,k≥1. (8.140)

For the field written as a complex numberEat the pointzwe have

E(z)=

∑M

k= 0

ak

zk+^1

+O(R/z)M+^1. (8.141)

FromFigure 8.7it can be seen that a worst case estimate forR/zis 2/3. In practice,
fewer than 20 multipole coefficients are necessary to obtain machine accuracy (32
bits).
In fact, it turns out to be possible to reduce the amount of work needed for the
force evaluation toO(N). The resulting method is called the fast multipole method
(FMM)–seeRefs.[62]and[63].

8.8 Langevin dynamics simulation

Most realistic physical systems are tractable only in amodel, in which the inter-
esting features of the system are highlighted and in which the less relevant parts
are either eliminated or treated in an approximate way. In this spirit we have for
example eliminated molecular degrees of freedom inSection 8.6by considering
(parts of) molecules to be rigid. Another example of this approach is the Langevin
dynamics technique, the subject of the present section. Consider a solution contain-
ing polymers or ions which are much heavier than the solvent molecules. As the
kinetic energy is on average divided equally over the degrees of freedom, the ions
or polymers will move much more slowly than the solvent molecules. Moreover,