Orthogonalisation and Diagonalisation

In both the DM and EDFT methods the dominant costs for large systems are the orthogonalisation of the trial wavefunctions to each other, and the subspace rotations required to diagonalise the Hamiltonian in the subspace of the current trial bands. Both of these operations scale as $N_GN_b^2N_k$ for a system with $N_G$ G-vectors, $N_b$ bands and $N_k$ k-points. As has been mentioned already, the number of k-points required decreases with system size, and for very large systems $N_k=1$ so the asymptotic scaling is cubic.

The orthogonalisation proceeds by constructing the band-overlap matrix, performing a Cholesky decomposition of this matrix to determine an orthogonalising transformation, and then applying this transformation. Both the construction of the band-overlap matrix and the applications of the transform are distributed over G-vectors and k-points, with very little communication required. The Cholesky decomposition is performed on a single node per k-point and the result broadcast, so is not distributed over G-vectors.

The subspace diagonalisation also requires a band-overlap matrix to be constructed, though this time it is between bands drawn from two different wavefunctions ($\psi$ and $\hat{H}\psi$). This matrix is then diagonalised to determine a diagonalising rotation, and the rotation applied to both the input wavefunctions. The first and last stages are distributed naturally over G- and k-points, but the diagonalisation itself is performed on a single node per k-point.