Linear-scaling algorithms

One recent development in DFT is the advent of linear scaling algorithms. These algorithms replace the Coulomb terms for distant regions of the molecule with multipole expansions. This results in a method with a time complexity of N for sufficiently large molecules. The most common linear scaling techniques are the fast multipole method (FMM) and the continuous fast multipole method (CFMM). 

DFT N With linear scaling algorithms (very large molecules)... 

If affordable, there is a range of very accurate coupled-cluster and symmetry-adapted perturbation theories available which can approach spectroscopic accuracy [57, 200, 201]. However, these are only applicable to the smallest alcohol cluster systems using currently available computational resources. Near-linear scaling algorithms [192] and explicit correlation methods [57] promise to extend the applicability range considerably. Furthermore, benchmark results for small systems can guide both experimentalists and theoreticians in the characterization of larger molecular assemblies. 

In quantum mechanical (QM) methods, the electrons are described explicitly. They require little or no parameterisation and offer the potential of high accuracy when compared with other methods. These methods are computationally expensive. The advances made in linear scaling algorithms, for example the... 

Keywords Coupled-cluster theory Local correlation methods Cluster-inmolecule formalism Linear scaling algorithms Single-reference coupled-cluster methods CCSD approach CCSD(T) approach Completely renormalized coupled-cluster approaches CR-CC(2,3) approach Large molecular systems Bond breaking Normal alkanes Water clusters... 

Assuming a linear scaling algorithm for the local energy, the compute time for molecular DMC calculations increase at least as fast as 0(M ). For bulk properties that are reported in energies per atom or per unit cell, the computed energies and errors may both be reduced by 1/M, so those calculations scale as 0(M ). 

Manten and Luchow (ML) created a linear scaling algorithm for evaluating two-body terms in the BH expansion. [162] The short range scaled distance function used by ML, = 1 — quickly approaches a constant value so that only linear number of terms in Eq. 9.57 need to be evaluated explicitly. 

A linear scaling algorithm for evaluation of three-body terms in the BH expansion has been described by Austin et al. [167, 168] Rewriting each term as a trace over a matrix product... 

S. Goedecker and L. Colombo Efficient linear scaling algorithm for tight-binding molecular dynamics, Phys. Rev. Lett. 73, 122-125 (1994). 

Segmental multipole moments contain extremely compact linearly scaling 0(N) representation of molecular charge distribution, which may otherwise occupy 0(N ) disk space in the form of electron density matrix. This feature should become more important in future, when advances in direct and linearly scaling algorithms will allow to produce routinely electron density matrices for very large molecular systems which could not be permanently stored. 

We describe here briefly the Hohenberg-Kohn-Sham density-functional theory for molecules and solids, " to set the stage for the discussion on the linear-.scaling algorithms. 

The solution of the eigenvalue equation (18) (or the calculation of the density matrix), and the construction of the h matrix are the two major computational tasks. What follows is mainly devoted to linear scaling algorithms for these two procedures. 

---