9.2 Scaling

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 $r_{\mathrm{reg}}$ and the density-kernel cut-off $r_K$.

9.2.1 System-size scaling

As mentioned in chapter 7, there are several steps in the calculation which are not strictly ${\cal O}(N)$, 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 ${\cal O}(N \log_m N)$. 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.

Figure 9.8: Variation of computational effort with system-size.

9.2.2 Scaling with density-matrix cut-off

We now consider the scaling with respect to the density-matrix cut-off $r_{\mathrm{cut}}$ which in practice is defined by two parameters; the support region radius $r_{\mathrm{reg}}$ and the density-kernel cut-off $r_K$. Two spherical support regions will overlap if the sum of their radii exceeds the distance between their centres. We assume that all support regions have the same radius $r_{\mathrm{reg}}$, and thus the number of support regions which overlap a particular region equals the number of region centres lying within a sphere of radius $2r_{\mathrm{reg}}$. For bulk solids this number will be proportional to the volume of the sphere i.e. proportional to $r_{\mathrm{reg}}^3$. 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 proportional to $r_{\mathrm{reg}}^3$. 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. $t_{\mathrm{comp}} \propto r_{\mathrm{reg}}^6$. This is often referred to as quadratic scaling with respect to the support region size (i.e. volume).

Table 9.3: Table showing the number of atoms lying within support regions of varying radii centred on atoms for some common cubic crystal structures.

Shell	# atoms	Radius $/a$	Diamond	FCC	BCC	Simple
1	4	$0.43301$	$\bullet$
2	12	$0.70711$	$\bullet$	$\bullet$
3	8	$0.86603$			$\bullet$
4	12	$0.82916$	$\bullet$
5	6	$1.00000$	$\bullet$	$\bullet$	$\bullet$	$\bullet$
6	12	$1.08972$	$\bullet$
7	24	$1.22474$	$\bullet$	$\bullet$
8	16	$1.29904$	$\bullet$
9	12	$1.41421$	$\bullet$	$\bullet$	$\bullet$	$\bullet$
10	24	$1.47902$	$\bullet$
11	24	$1.58114$	$\bullet$	$\bullet$
12	12	$1.63936$	$\bullet$
13	24	$1.65831$			$\bullet$
14	8	$1.73205$	$\bullet$	$\bullet$	$\bullet$	$\bullet$
15	24	$1.78536$	$\bullet$
16	48	$1.87083$	$\bullet$	$\bullet$
17	36	$1.92029$	$\bullet$
18	6	$2.00000$	$\bullet$	$\bullet$	$\bullet$	$\bullet$
19	12	$2.04634$	$\bullet$
20	36	$2.12132$	$\bullet$	$\bullet$
21	28	$2.16506$	$\bullet$
22	24	$2.17945$			$\bullet$
23	24	$2.23607$	$\bullet$	$\bullet$	$\bullet$	$\bullet$
24	36	$2.27761$	$\bullet$
25	24	$2.34521$	$\bullet$	$\bullet$
26	24	$2.38485$	$\bullet$
27	24	$2.44949$	$\bullet$	$\bullet$	$\bullet$	$\bullet$
28	36	$2.48747$	$\bullet$
29	72	$2.54951$	$\bullet$	$\bullet$
30	36	$2.58602$	$\bullet$
31	32	$2.59808$			$\bullet$
32	24	$2.68095$	$\bullet$	$\bullet$
33	48	$2.73861$	$\bullet$
34	24	$2.77263$	$\bullet$	$\bullet$

The argument follows in precisely the same manner for the density-kernel cut-off, replacing $2r_{\mathrm{reg}}$ by $r_K$. In general, as observed in section 9.1.1, $r_K \approx 2 r_{\mathrm{reg}}$ 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 $r_{\mathrm{cut}}$ i.e. $t_{\mathrm{comp}} \propto r_{\mathrm{cut}}^6$.

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 $t_{\mathrm{comp}} \propto r_{\mathrm{cut}}^2$, and this suggests that these linear-scaling methods may be more suited to studying molecular rather than crystalline systems.