In this section we consider the scaling of the method, firstly with respect to the system-size, and secondly with respect to the localisation region radius and the density-kernel cut-off .
As mentioned in chapter 7, there are several steps in the calculation which are not strictly , such as the calculation of the structure factor, the calculation of the ion-ion interaction energy (by Ewald's method [175,176,177,178]) and possibly the calculation of the energy correction. All of these operations need only be performed once for each ionic configuration, and so do not contribute significantly to the total computational effort. However, there are a number of FFTs within the method which require an effort which scales as . To verify that these operations do not spoil the linear-scaling of the rest of the method, we plot the CPU time required per iteration in figure 9.8 and see that it is indeed linear with respect to system-size as required.
We now consider the scaling with respect to the density-matrix cut-off
which in practice is defined by two parameters;
the support region radius
and the density-kernel
Two spherical support regions will overlap if the sum of their radii
the distance between their centres. We assume that all support regions have
the same radius
, and thus the number of support
regions which overlap a particular region equals the number of region
centres lying within a sphere of radius
. For bulk solids
this number will be proportional to the volume of the sphere i.e. proportional
. Table 9.3 allows the precise number of
overlaps to be determined for the case of atom-centred support regions
in several common crystal structures. In the sparse overlap matrix, the
number of non-zero elements in each row or column is therefore also
. For sparse matrix multiplication, the
computational effort scales quadratically with the number of non-zero
elements per row (and linearly with the rank) so that we expect the method
to scale with the sixth power of the support region radius i.e.
. This is often referred to
as quadratic scaling with respect to the support region size (i.e. volume).
The argument follows in precisely the same manner for the density-kernel cut-off, replacing by . In general, as observed in section 9.1.1, when the energy is converged with respect to both parameters, so that the overlap matrix and density-kernel will generally share similar sparse structure. In bulk crystals, we thus expect the computational effort to scale with the sixth power of the density-matrix cut-off i.e. .
In certain systems, however, this scaling may be different. For example, in long linear molecules e.g. hydrocarbon chains, which have an essentially one-dimensional structure, each support region will overlap a number of others which scales only linearly with the radius. In this case , and this suggests that these linear-scaling methods may be more suited to studying molecular rather than crystalline systems.