Davidson method

E. Davidson. Method and composition for scavenging sulphide in drilling fluids. Patent WO 0109039A, 2001. 

Davidson Method for Computing Eigenvalues of Sparse Symmetrical Matrices. 

This defines the standard Davidson method. A very common improvement is the Davidson-Liu method, which uses several vectors at a time, and a different, diagonal, preconditioner for each root ... 

Well-known procedures for the calculation of electron correlation energy involve using virtual Hartree-Fock orbitals to construct corresponding wavefunctions, since such methods computationally have a good convergence in many-body perturbation theory (MBPT). Although we know the virtual orbitals are not optimized in the SCF procedure. Alternatively, it is possible to transform the virtual orbitals to a number of functions. There are some techniques to do such transformation to natural orbitals, Brueckner orbitals and also the Davidson method. 

In the Davidson method, one approximates A by the current iteration s eigenvalue, and H is assumed to be diagonally dominant so that 6 can be approxi-... 

Liu showed how to extend Davidson s method to solve for several roots simultaneously,174 leading to what is called the Simultaneous Expansion Method, the Davidson-Liu method, or the block Davidson method. The detailed Davidson Liu algorithm, adapted from ref. 174, is presented in Figure 5. 

The expansion coefficients are eigenvectors of the interaction matrix. Sparse matrix methods are used since, as the size of the expansion increases, more and more matrix elements are zero. An implementation of the Davidson method [14] is used for large cases. Since it is based on the multiplication of the interaction matrix by a vector, the method can readily be parallelized [15]. 

Even with standard restart methods such as ARRACK and TRLan, the memory demand can still remain too high in some cases. Hence, it is important to develop a diagonalization method that is less memory demanding but whose efficiency is comparable to ARRACK and TRLan. The Chebyshev-Davidson method [23] was developed with these two goals in mind. Details can be found in [23]. The principle of the method is to simply build a subspace by a procedure based on a form of Block-Davidson approach. The Block-Davidson approach builds a subspace by adding a window of preconditioned vectors. In the Chebyshev-Davidson approach, these vectors are built by exploiting Chebyshev polynomials. 

The first step diagonalization by the block Chebyshev-Davidson method, together with the Chebyshev-filtered subspace method (Algorithm 6.3), enabled us to... 

The goal of the computations is to use PARSEC to do SCF calculafions for large systems which were not studied before. We did not use different processor numbers to solve the same problem. Scalability is studied in [28] for the precondifioned Davidson method, we mentioned that the scalability of CheFSI is better than eigenvector-based methods because of the reduced reorthogonalizations. 

The efficiency supplied by the Davidson method is that the main work is in the matrix-vector multiplications, which scales as M, rather than the of direct diag-onalization. The biggest problem is the storage of the Hamiltonian matrix, which can be written to disk and read in row by row, or in batches of matrix elements if it is sparse. Thus, we do not need to keep the Hamiltonian matrix in memory to obtain its eigenvectors. 

The Davidson method has proved highly successful in electronic-strueture theory. Still, this method should be applied with some caution - in particular, if attempts are made at improving the approximate Hamiltonian Hq. Thus, from (11.5.25), we note that the Davidson step is not orthogonal to In fact, in the limit when Ho becomes the full matrix H, the Davidson step becomes parallel to C >... 

When only the Davidson part of the quasi-Newton step is used, we observe nearly identical convergence if all vectors are retained in the eigenvector subspace. With truncation of the subspace, the convergence of the Davidson method degrades somewhat relative to the quasi-Newton method. Thus, at the equilibrium geometry, the Davidson method converges to Eh in 15 iterations with two vectors in the subspace, compared with the 12 iterations for the quasi-Newton method. 

Comparing Tables 11.3 and 11.4, we find that, in terms of macro iterations, the Newton method converges faster than the quasi-Newton method. The quasi-Newton method works better than the Newton method in the first few iterations, but the local cubic convergence of the Newton method then takes over and ensures that this method gives the smallest number of macro iterations. However, since each Newton iteration is an order of magnitude mote expensive than each quasi-Newton or Davidson iteration, the quasi-Newton and Davidson methods are far more cost-effective. 

We now solve the Cl eigenvalue problem using the Davidson method in a two-dimensional subspace. Each iteration consists of the following steps ... 

Compare E — Ecnv. lIRnll and C — Ccnvil for = 1 and = 2 in the Newton optimization of Exercise 11.11.5. Do the errors exhibit the expected cubic convergence Compare with the errors of the Davidson method. 

All three error measures in Table IIS.11.3 show cubic convergence. Comparing with the Davidson method in Table 1 IS. 11.2, we find that, for this particular system, one Newton iteration corresponds to three Davidson iterations. 

---