Divide-and-conquer methods

Van der Vaart A, V Gogonea, SL Dixon, KM Merz, Jr (2000) Linear scaling molecular orbital calculations of biological systems using the semiempirical divide and conquer method. J. Comput. Chem. 21 (16) 1494-1504... 

The solid-state equivalent of the divide-and-conquer method has been known for a long time. The natural subunits are the unit cells, which are repeated many times to form the macroscopic crystal. The wave equations need to be solved only for a single cell. The connection between the cells is made by multiplying by the factor exp (ik-R) when one goes from any point in one unit cell to the corresponding point in another unit cell. R is a vector marking the distance of the second cell from the first and k is a wave vector in reciprocal space. This... 

Stoye, J. (1998) Multiple Sequence Alignment with the Divide-and-Conquer Method, Gene 211 GC45-56. 

So far, we discussed the efficacy of the divide-and-conquer method in the abstract sense. With regards to pharmacogenomics, such efficacy may manifest itself in the form of better quality, faster convergence to a solution, or better cost. Whether it actually accomplishes one or more of the aforementioned objectives depends on the... 

The divide-and-conquer method [34,35] was the first Kohn Sham algorithm which delivered linear scaling computational costs that grow linearly with the size of the system. In this technique, one first projects the density matrix onto a basis set, typically... 

It is clear that this construction has given the desired nearsightedness for the density matrix yyi-sj is zero whenever Ry / > Rh [39]. Moreover, because the cost of the method is proportional to the number of subsystems, and the number of subsystems may be chosen to be proportional to the size of the molecule, the cost of the divide-and-conquer method is proportional to the size of the molecule. 

Yang s divide-and-conquer method is reviewed and shown to be as accurate as the conventional Kohn-Sham method and to be a practical algorithm for large molecule calculations. The working mechanism of the method is thoroughly examined. 

Two years ago Yang developed a divide-and-conquer strategy to do the DFT computations [43], By projecting the Hamiltonian into subspaces, he was able to divide a large system into smaller subsystems, and solve a KS-like equation for each subsystem. Recently, Zhou has provided an alternative construction of the divide-and-conquer method by projecting the solutions of KS equations with different basis sets associated with each subsystem [44]. The divide-and-conquer method is shown to be as rigorous as the conventional KS method. As far as electron density and energy density are concerned the divide-and-conquer method is different from the conventional KS method only by the way in which the basis sets are truncated. The rest of this section will review the divide-and-conquer method and try to provide some reasons why the method should work. 

Construction of the divide-and-conquer method by projection of charge density and energy density... 

This construction, due to the author, is the result of an effort to better understand the divide-and-conquer method newly formulated by Yang [43,44]. First, divide a molecule into several subsystems. Then, choose a complete basis set (x ( r) for each subsystem a in such a way that the centers of all basis functions are within or near a. Because (x (r) is complete, the KS equation can be solved exactly using this basis set. Eigenvalues and eigenstates are respectively denoted as e (. This solution is... 

Conventional KS method <— Even basis set truncation Divide-and-conquer method <— Uneven basis set truncation... 

Thus, a common basis set for all subsystems will recover the conventional KS method. In this case the divide-and-conquer method will deliver the conventional KS solution, including the KS eigenvalues and the KS orbitals. The computational efficiency associated with the divide-and-conquer method arises from different basis sets for different subsystems. The KS orbitals are avoided in this case. 

Several remarks are in order about the divide-and-conquer method. First, the matchup of basis set with projection weight in eqs.(19) and (20) is critical for accurately projecting the KS solution. For complete basis sets this is not a problem. 

The divide-and-conquer method can be constructed such that the Thomas-Fermi type models are the consequences of the method. This will be the third construction of the method. Define a projected Hamiltonian for subsystem a using an operator 0 ... 

The usefulness of this divide-and-conquer method is illustrated below by a series of calculations on the model system H-(-C=C-)-H. This system is convenient for testing various choices of projection weights, or basis sets, or Fermi parameter. The tests given here extend previous tests [43,57]. 

Figure 1 Flow chart of the divide-and-conquer method. The boxes with single borderlines are carried out at subsystem level and those with double borderlines at the global level. The iterative procedure is represented by shadowed arrows. 

For simplicity, the LDA exchange-correlation functional is used. The correlation is the VWN parametrization of Monte Carlo result of Ceperley and Alder for a free electron gas [48,61]. The calculation is not spin-polarized. The purpose here is to show the mechanism of the divide-and-conquer method. While nonlocal corrections to Exc[p] and spin-polarization are instrumental to get results of chemical accuracy, none of these is expected to affect the basic mechanism of the method. 

Basis sets affect the performance of P ( r) in a subtle way. In fact, the requirement for (g (r) to give a good matchup is that g (r) decays much faster than the partial molecular density contributed by the basis functions centered at atoms in subsystem a. The bigger the basis sets are the less important the matchup will be. The extreme case will be that all subsystem basis sets are complete. In this case the matchup problem disappears. This is the KS limit solution. Or, all subsystems use a common basis set. The divide-and-conquer method reduces to the conventional KS method. The projection weights do not play any role in this situation. 

For finite temperature DFT the Fermi function in eqs.(l 1) and (12) is exact [43], The divide-and-conquer method gives the same results as the conventional KS method does except the orbitals. The parameter /3 now gets a physical meaning. It is the inverse of the temperature. 

Balance among different basis sets is as important in the divide-and-conquer method as the basis set balance in the conventional ab initio calculations. Unbalanced basis sets will lead to nonphysical charge shifts. Take N2 molecule as an example. Putting more basis functions on one N atom than on the other will result in a nonzero dipole in this molecule. This artifact exists in both the divide-and-conquer method and the conventional methods. The experiences of balancing basis set from conventional methods can be used directly in the divide-and-conquer calculations. 

A series of homologous molecules H-(-C=C-)-nH with n = 3, 5, 10, 13, and 15 are examined. The advantage of the divide-and-conquer method over the conventional KS... 

Theoretically, the divide-and-conquer method scales linearly with the molecular size before the Coulomb and/or nuclear terms dominate. Both terms scale as NlnN where... 

The divide-and-conquer methods [88-90] are based on a partitioning of the density matrix. The overall electronic stmcture calculation is decomposed into a series of relatively inexpensive, standard calculations for a set of smaller, overlapping subsystems. A global description of the full system is then obtained by combining the information from all subsystem density matrices. 

Yang and co-workers developed a divide-and-conquer method that combines calculations done on overlapping regions of the molecule [T.-S. Lee,D. M. York, and W. Yang,/. Chem. Phys., 105,2744 (1996) S. L. Dixon and K. M. Merz,/. Chem. Phys., 107, 879 (1997)]. 

---