Linear-Scaling Techniques in Computational Chemistry and Physics

This paper reviews the use of plane-wave based methods to decrease the scaling of the most time-consuming part in molecular electronic structure calculations, the Coulomb interaction. The separability of the inverse distance operator allows the efficient calculation of the Coulomb potential in momentum space. Using the Fast Fourier Transform, this can be converted to the real space in essentially linearly scaling time. Plane wave expansions are periodic, and are better suited for infinite periodic systems than for molecules. Nevertheless, they can be successfully applied to molecules, and lead to large performance gains. The open problems in the field are discussed.

The fragment molecular orbital (FMO) method is a computational scheme applied to the conventional molecular orbital theories, which reduces their scaling from N ³… N ⁷ to a nearly linear scaling, where N is the system size. FMO provides an accurate treatment of large molecules such as proteins and molecular clusters, and it can be efficiently parallelized to achieve high scaling on massively parallel computers. The main purpose of this chapter is to focus on the derivation of the equations and to provide a concise mathematical description of FMO. A brief summary of the recent applications of FMO is also given.

All traditional methods for electron correlation share a steep power law dependence on the molecular size. This high scaling prohibits the use of these methods to large systems in spite of the very impressive advances in computer technology over the past decades. Clearly, this problem cannot be solved with improvements of computers alone, and new methods reducing the power law scaling to one or near one must be developed. In this chapter some linear of low scaling methods for electron correlation will be reviewed. The focus will be on the linear scaling MP2 methods, but other more accurate correlation methods will also be briefly discussed. In addition, the very efficient RI-MP2 will be discussed even though the high power law scaling of conventional MP2 has not been reduced. A discussion of the RI-MP2 method has been included since it is perhaps an order of magnitude more efficient than other efficient MP2 methods. The RI or density fitting approach has now been combined with the local correlation method, and the RI-LMP2 method exhibits linear scaling with the size of the system. Most of the methods discussed herein are based on the local correlation method introduced by Pulay and Saebø in the early eighties and developed further by Schütz, Werner and co-workers. The topic was reviewed in 2002 and this review will focus on the more recent advances in this field. A new linearly scaling LMP2 approach yielding essentially identical results to conventional canonical MP2 will be described, and MP2 calculations with around 5,000 contracted basis functions have been performed without density fitting using this approach.

With the aim of developing linear-scaling methods, we discuss perturbative approaches designed to avoid diagonalization of large matrices. Approximate molecular orbitals can be corrected by perturbation theory, in course of which the Laplace transformation technique proposed originally by Almløf facilitates linear scaling. The first order density matrix P corresponding to a one-electron problem can be obtained from an iterative formula which preserves the trace and the idempotency of P so that no purification procedures are needed. For systems where P is sparse, the procedure leads to a linear scaling method. The algorithm is useful in course of geometry optimization or self-consistent procedures, since matrix P of the previous step can be used to initialize the density matrix iteration at the next step. Electron correlation methods based on the Hartree-Fock density matrix, without making reference to molecular orbitals are commented on.

Recently, the authors implemented the linear-scaling divide-and-conquer (DC) quantum chemical methodologies into the GAMESS-US package, which is available without charge. In this Chapter, we summarized recent developments in the DC methods, namely, the density-matrix-based DC self-consistent field (SCF) and the DC-based post-SCF electron correlation methods. Especially, the DC-based post-SCF calculation is considerably efficient, i.e., its computational time achieves near-linear scaling with respect to the system size [O(N ¹)] and the required memory and scratch sizes are hardly dependent on the system size [O(N ⁰)]. Numerical assessments also revealed the reliability of the DC methods.

The Additive Fuzzy Density Fragmentation (AFDF) principle provides the basis for the linear scaling Adjustable Density Matrix Assembler (ADMA) method, developed for detailed, ab initio quality macromolecular electron density computations, directed primarily towards protein studies. The same principle is the basis for novel approaches to the local analysis of electron density fragments, such as functional groups and regions surrounding reactive centers in various biomolecules. The basic theoretical developments as well as the implementation of the ADMA and related methods are subject to the conditions represented by the Holographic Electron Density Theorem: in any non-degenerate ground state, any positive volume local part of the electron density contains the complete information about the entire, boundaryless molecule. This represents a limitation on the transferability of molecular fragments, however, by a fuzzy fragmentation, some of the difficulties can be circumvented. Approximate transferability is a viable option if the relations between local and global properties are properly taken into account. Specifically, the interplay between local and global molecular properties, as manifested, for example, by symmetry properties and the topological shape constraints on molecular features has a strong influence on molecular energies. A better understanding of the interactions between local and global features also leads to fragment-based combinatorial quantum chemistry approaches. A general framework for such studies can be formulated based on the insight obtained by macromolecular quantum chemistry computations using the linear scaling ADMA method.

The chemical motivation and the role of molecular fragmentation schemes in various linear scaling quantum chemical computational methods are discussed, with special emphasis on fragmentation based on the properties of molecular electron densities. The special significance of functional groups in fragment selection, the concept and use of delocalized fragments, the “Procrustes Fragmentation” and “Multi-Procrustes Fragmentation” schemes, and the utility of trigonometric weighting in reducing potential errors due to the bias introduced by fragment selection are discussed. The special fragmentation possibilities implied by the Additive Fuzzy Density Fragmentation Principle, and their application in the context of the Adjustable Density Matrix Assembler (ADMA) method are also discussed.

Quantum chemical calculations of very large systems still pose major challenges due to the formidable scaling behavior of standard methods with system size. Here, we will describe how the concept of separating short- and long-range interactions can be used to make such calculations possible nonetheless at least in an approximate way. In mixed quantum mechanical/molecular mechanical (QM/MM) and fragment-based quantum chemical methods, the local surroundings are considered explicitly whereas other parts further away are neglected or included with a lower level of theory, e.g. as interactions with point charges. Different methods to combine these two descriptions, so-called embedding schemes, are outlined. Additionally, the border region problem, how subsystems describable by quantum mechanics can be generated by cleaving and saturating bonds connecting atoms located in the different regions, and proposed solutions are discussed. Finally, with the fragment-based adjustable density matrix assembler (ADMA) method as example, the capacities but also some limitations of the presented approaches will be presented using different test systems.

We present the linear scaling elongation method for Hartree-Fock and Kohn-Sham electronic structure calculations of either periodic or aperiodic quasi-one-dimensional systems. Linear scaling is achieved through two key computational features: (1) regional localization of molecular orbitals; and (2) a two-electron integral cutoff technique combined with quantum fast multipole evaluation of non-negligible long-range integrals. The accuracy and timing of the method is demonstrated for several systems of interest such as polyglycine and BN nanotubes. Future developments of both a technical and methodological nature are noted including the extension to higher dimensionality as well as higher level wave function treatments.

Divide-and-conquer (DC) type methods are being actively developed in order to break the bottleneck of high scaling order of ab initio calculations of large molecules. Molecular Tailoring Approach (MTA) is one of such early attempts, which scissors the parent molecular system into subsystems (fragments). The properties of these subsystems are stitched back in order to estimate those for the parent system. Inclusion-exclusion principle from set theory is incorporated into MTA, which allows accurate estimation of electronic energy, energy-gradients and Hessian. This Chapter summarizes the algorithm, equations as well as basic parameters for obtaining an optimal fragmentation for a given molecule. The fragmentation in MTA is exclusively based on distance-criterion allowing its application to a general class of molecules. Further, the versatility of this method with respect to the level of theory [Hartree-Fock (HF) method, Møller-Plesset second order perturbation theory (MP2) and Density Functional Theory (DFT)] as well as the basis set is illustrated. Apart from earlier benchmarks, a few new test cases including geometry optimization of variety of molecules, benzene clusters, polyaromatic hydrocarbons, metal cluster and a protein with charged centers are presented in this Chapter.

We discuss algorithms that can be used to calculate electron densities using computer resources – memory and processor time – that increase only linearly with system size. We focus on the Hartree-Fock and density functional theories and calculations using Gaussian basis sets. However, many of the approaches discussed here are applicable also for other methods and for any local basis. Particular attention is directed towards error control and how to avoid the use of the ad-hoc selected parameters and threshold values often associated with computational approximations employed to reach linear scaling. The discussed aspects include multipole methods, linear scaling computation of the Hartree-Fock exchange and density functional theory exchange-correlation matrices, hierarchic representation of sparse matrices, and density matrix purification. The article also describes how these different parts are put together to achieve linear scaling for the entire Hartree-Fock or density functional theory calculation, controlling errors in the self-consistent field procedure by considering rotations of the occupied subspace.

Local methods for the description of electron correlation in ground and electronically excited states of molecules, as implemented in the MOLPRO system of ab initio programs, are reviewed. Recent improvements in the performance of the local method resulting from an implementation of the density-fitting technique for all electron-repulsion integrals are discussed. Local fitting approximations lead to linear scaling of CPU time and disk space with molecular size, and allow for a significant increase of the size of molecules and basis sets that can be treated by the local MP2, CCSD, and CCSD(T) ab initio methods. Recent extensions of these methods to open-shell systems, as well as the inclusion of explicitly correlated terms are described. It is demonstrated that the latter lead to a drastic improvement of the accuracy of local methods. A local treatment of electron excitations within the EOM-CCSD and CC2 theories, as well as a local description of first- and second-order molecular properties are also discussed. Finally, we present some illustrative applications of the outlined methods.

When dealing with large biological systems speed determines the utility of the computational method. Therefore in order to bring quantum-mechanical (QM) methods to computational studies of biomolecules it is necessary to significantly reduce their resource requirement. In this light semiempirical QM methods are particularly encouraging because of their modest computational cost combined with potentially high accuracy. However, even semiempirical methods are frequently found to be too demanding for typical biological applications which require extensive conformational sampling. Significant speed up is obtained in the linear scaling LocalSCF method which is based on the variational finite localized molecular orbital (VFL) approximation. The VFL provides an approximate variational solution to the Hartree-Fock-Roothaan equation by seeking the density matrix and energy of the system in the basis of compact molecular orbitals using constrained atomic orbital expansion (CMO). Gradual release of the expansion constraints leads to determination of the theoretically most localized solution under small non-orthogonality of CMOs. Validation tests confirm good agreement of the LocalSCF method with matrix diagonalization results on partial atomic charges, dipole moment, conformational energies, and geometry gradients while the method exhibits low computer memory and CPU time requirements. We observe stable dynamics when using the LocalSCF method.

We review some recursive Fermi operator expansion techniques for the calculation of the density matrix and its response to perturbations in tight-binding, Hartree-Fock, or density functional theory, at zero or finite electronic temperatures. Thanks to the recursive formulation, the expansion order increases exponentially with the number of iterations and the computational cost scales only linearly with the system size for sufficiently large sparse matrix representations. The methods are illustrated using simple models that are suitable for small numerical experiments.

A Green function (GF) linear-scaling technique based on the Korringa-Kohn-Rostoker (KKR) multiple scattering method is presented for Hohenberg-Kohn-Sham density functional calculations of metallic systems. Contrary to most other methods the KKR-GF method does not use a basis-set expansion to solve the Kohn-Sham equation for the wavefunctions, but directly determines the Kohn-Sham Green function by exploiting a reference system concept. An introduction to the KKR-GF method is given and it is shown how linear-scaling is obtained by the combined use of a repulsive reference system, which leads to sparse matrix equations, iterative solution of these equations and a spatial truncation of the Green function in the sense of Kohn’s principle of nearsightedness of electronic matter. The suitability of the technique for metallic systems with thousands of atoms is illustrated by model calculations for large supercells and its usefulness for computing on massively parallel supercomputers is discussed.