The most straightforward approach to the evaluation of the
Laplacian operator applied to a function at every grid point
is to approximate the second derivative by finite differences of
increasing order of accuracy [7]. For
example, the
part of the
Laplacian on a grid of orthorhombic symmetry is

In principle, for well behaved functions, the second order form of equation (5) should converge to the exact Laplacian as . Therefore to increase the accuracy of a calculation one would need to proceed to smaller grid spacings. However, in most cases of interest, this is computationally undesirable and instead, formulae of increasing order are used to improve the accuracy at an affordable cost [8]. Chelikowsky et al. [9], in their finite difference pseudopotential method, have tested the finite difference expression for up to on calculations of a variety of diatomic molecules and have suggested as the most appropriate for their purpose, as the higher orders did not provide any significant improvement.

Alternative discretisations of the Laplacian operator are possible, such as the Mehrstellen discretisation of Briggs et al. [5]. This is a fourth order discretisation that includes off-diagonal terms, but only nearest neighbours to the point of interest. It is more costly to compute than the standard fourth order formula of equation (5) and it is still not clear whether its fourth order is sufficient. One may also use FD methods on a grid with variable spatial resolution, such as that of Modine et al. [10] which is denser near the ionic positions. Such a scheme, however, has the added overhead of a transformation of the Laplacian from Cartesian to curvilinear coordinates. In this paper we use only the FD scheme of equation (5).

The FD approach has desirable properties, both in terms of computational scaling and parallelisation. The Laplacian in the FD representation is a near-local operator, becoming more delocalised with increasing order. Therefore, the cost of applying it to grid points is strictly linear (compared to for Fourier transform methods). Also, as a result of its near-locality, ideal load balancing can be achieved in parallel implementations by partitioning the real space grid into subregions of equal size and distributing them amongst processing elements (PEs) while requiring little communication for applying the Laplacian at the bordering points of the subregions.

If represents the size of the system, then the number of support functions will be proportional to and so will the total number of grid points in the simulation cell, resulting in a total computational cost proportional to for the application of the Laplacian on all support functions. More favourable scaling can be achieved by predicting the region in space whithin which the values of a particular function will be of significant magnitude and operating only on this region [4,11]. Linear-scaling can be achieved by strictly restricting from the outset the support functions to spherical regions centred on atoms [12]. In this case, the cost is with being the cost of applying the Laplacian on the points of a spherical region, which is constant with system size.

FD methods nevertheless have disadvantages that
do not appear in the plane-wave formalism. Firstly, there
is no *a priori* way of knowing whether a
particular order of FD approximation will be sufficient
to represent a particular support function
accurately. In addition, while plane-wave methods
can handle different symmetry groups trivially
through the reciprocal lattice vectors of the
simulation cell, real space implementations need to
consider every symmetry separately and require
considerable modifications to the code and higher
computational cost. Briggs et al. [5] have
demonstrated this difficulty by performing calculations
with hexagonal grids while most common applications
of real space methods in the literature are limited
to grids of cubic or orthorhombic
symmetry [4,6,9,12].

The computational cost for the calculation of the Laplacian of a single support function with the FD method scales as where is the number of grid points within the support region, and is the number of grid points along the support region diameter and is proportional to . This estimate of cost includes all the nonzero values of the Laplacian, which in general occur not only at the grid points inside the support region but also at points outside, up to a distance of points from the region's boundary. It is important to include the contribution to the Laplacian from outside the support region in the sum of equation (4) in order to obtain the best possible accuracy for a given order and also to ensure the Hermiticity of the discretised representation of the Laplacian, , and hence of the kinetic energy matrix elements .