[CP2K:126] computational scaling in QS

[Fawzi Mohamed]

On Jun 6, 2007, at 4:55 PM, Nichols A. Romero wrote:

> Hi,

Hi

> I was hoping that I can get some clarification about the scaling in  
> QS. I read through
> Comp. Phys. Comm. 167 (2005) 103. My background is PW methods.
>
> There are two ways to obtain the KS ground state in QS:
> 1. SCF + traditional diagonalization (TD)
> - The construction of the KS matrix is approximately O(N ln N) < O  
> (N^(1+epsilon))
> - TD scales as M^3
> N  is the number of occupied orbitals ??

yes, but you are right that the use of N is a little mixed, as  
sometime it is used for the number of atoms, sometime for the number  
of electron or occupied orbitals.
Note that for a fixed system composition O(N_atom) <=> O(N_el)

> M is the number of basis functions
>
> Fig. 4 on p. 110 of the article uses N only, instead of M and N. I  
> guess one parameter
> indicative of system size was used instead of multiple parameters.

exactly (as said before O(N_atom) <=> O(N_el))

> Also, could someone comment on the memory requirement using SCF + TD.

OT stores only MxN matrixes (C) and filtered (sparse) MxM matrixes  
(for H,S, and the sparse P).
The filtered matrixes have the sparsity pattern of the overlap matrix S.
The sparse P can be used only to calculate the density n(r), not the  
non local n(r,r').
The grids scale linearly with the volume, and thus normally linearly  
with N , and are distributed, but can get very big with GPW and hard  
elements (if the cutoff has to be big).

TD furthermore stores full MxM matrixes, thus that gives its memory  
requirement

> 2. OT
> - On p. 117, the text states that in the most optimal situation the  
> method
> scales as M*N^2 and M^2*N in the worst case (non-sparse) scenario.
> - The memory scales as O(M*N) which I is also similar to a PW method
> but with a localized basis M is substantiall smaller. I imagine the  
> other terms
> that contribute to the memory scaling, e.g. potential, charge  
> density, etc.
> are negligible ??

the only real other tem are the grids, which can actually be rather  
large, depending on the system.
On large systems the cubic term of the matrixes dominates, and  
whereas you can still perform calculations using OT it is not  
possible with TD.

Fawzi