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.