Computational Scaling of the Configuration Interaction Method with System Size

C. David Sherrill
School of Chemistry and Biochemistry
Georgia Institute of Technology

September 1996

At times there appears to be a confusion in the literature regarding the computational scaling of the configuration interaction method. For example, Gershgorn and Shavitt claim [1] that CI scales as ${\cal O}(n^{m+2})$, where n is the number of orbitals, and m is the excitation level (e.g., 2 for CISD). However, it is commonly held that CISD actually scales as ${\cal O}(n^6)$; for CISDTQ, various scalings are given, but the most common one is ${\cal O}(n^{10})$. This would seem to imply a general scaling rule of ${\cal O}(n^{2m+2})$, in contradiction to the former rule. These notes explain the scaling of the CI method and demonstrate that, depending on circumstances, either limit may be appropriate. For the present purposes, it will suffice to focus simply on Slater determinants rather than other possible N-electron basis functions, such as configuration state functions (CSF's).

For present purposes, it is sufficient to work with spin orbitals. Typically, the dimension of the CI space is dominated by determinants with the maximum excitation level, m. Thus,

$$N_{det} \sim \left( \begin{array}{c} N \\ m \end{array} \ri... ...n_v \\ m \end{array} \right) \sim \frac{1}{(m!)^2} N^m n_v^m,$$ (1)

with n_v orbitals unoccupied in the reference (i.e., virtual orbitals). Most CI procedures solve only for the lowest or lowest few eigenvectors, via an iterative procedure. In such situations, the scaling is much less than the ${\cal O}(N_{det}^3)$ typical of standard matrix diagonalization methods. The most expensive step in iterative procedures such as the Davidson method [2] is the construction of the so-called ${\sigma}$ vectors,

$${\mathbf \sigma}_i = {\mathbf H} {\mathbf b}_i$$ (2)

where b_i belongs to a set of trial vectors which is expanded each iteration until convergence is reached. If the Hamiltonian matrix H were formed directly, this procedure would require ${\cal O}(N_{det}^2)$ operations. This is never actually done because the storage requirements would be too great, and such an approach ignores the fact that the Hamiltonian contains only two-body terms, so that the majority of the matrix elements are zero.

Each element of a trial vector b_i need only be multiplied by the nonzero elements of H. The Hamiltonian will connect a maximally excited determinant with other maximally excited determinants and with other determinants having excitation level $m \geq m' \geq m-2$. The number of interacting determinants is roughly

$$\left( \begin{array}{c} m \\ 2 \end{array} \right) \left( \... ...in{array}{c} N - m \\ 2 \end{array} \right) + m^2 n_v (N-m),$$ (3)

which we further approximate as

$$\frac{1}{4} m^2 (n_v + m)^2 + \frac{1}{4} m^2 (N - m)^2 + m^2 n_v (N - m).$$ (4)

Each element in b_i must be multiplied by the relevant nonzero matrix elements, leading to an overall operation count on the order of

$${\cal O}(N^m n_v^m \left\{ m^2 n_v^2 + m^2 N^2 + m^2 N n_v \right\}).$$ (5)

Except for full CI, we typically expect N, n_v >> m. Furthermore, we almost always have n_v > N, so that the leading term becomes ${\cal O}(N^m n_v^{2+m})$. Thus the final results are

$${\cal O}(N^m n_v^{2+m}) = \left\{ \begin{array}{ll} n^{2m+2... ... \\ n^{m+2} & \mbox{if $n_v >> N, m$ }. \end{array} \right.$$ (6)

These results show that CISD and CISDTQ will scale as ${\cal O}(n^6)$and ${\cal O}(n^{10})$, respectively, for typical cases, and as ${\cal O}(n^4)$ and ${\cal O}(n^6)$ for very large numbers of orbitals or a small number of active electrons.

For very high levels of excitation, including full CI, the number of interacting matrix elements for a given determinant becomes approximately N² n², so that the computational cost becomes roughly

$${\cal O}^{FCI}(N_{det} N^2 n^2)$$ (7)

where we have replaced the term N^m n_v^m with the actual number of determinants, N_det. For comparison, the determinant full CI algorithm of Knowles and Handy [3] scales as ${\cal O}(N_{det}n^4)$, while the algorithm of Olsen et al. [4] and similar approaches scale as ${\cal O}(N_{det} N^2 (n-N/2)^2)$ for a closed-shell system.