Jak skaluje się funkcjonalna teoria gęstości z rozmiarem systemu?

Teoretycznie, w jaki sposób czas na wykonanie obliczeń teorii funkcjonalnej gęstości (DFT) wraz z liczbą elektronów? Interesują mnie „typowe” implementacje DFT, takie jak VASP, ABINIT itp., A nie kody O (N).

Najprostszą poprawną odpowiedzią jest to, że DFT jest w . Wynika to z idei, że ostatecznie przekątnasz hamiltonian o wymiarze proporcjonalnym do liczby wyborów, a przekątna jest technicznie O ( n 3 ) .$O(N_e^3)$$O(n^3)$

W rzeczywistości DFT jest zbiorem kroków, a różne kroki ograniczają szybkość w innym kontekście. Jeśli ograniczymy się do fali płaskiej (PW) DFT (VASP, ABINIT, QE i inne), możemy podać mocniejsze stwierdzenia. Ważnym pomysłem do zrozumienia dla kodów PW DFT jest to, że Hamiltonian nigdy nie jest przechowywany jako duża matryca; zamiast tego działanie operatora hamiltonowskiego jest obliczane i stosowane w iteracyjnych diagonalizatorach iteracyjnych (gradient sprzężony, Davidson itp.). Te diagonalizatory są formalnie , gdzie M $O(n_e MV)$$MV$ jest kosztem obliczania działania hamiltonianu, ale biorąc pod uwagę ich rolę w większym samowystarczalnym algorytmie, mają one tendencję do działania znacznie szybciej.

Proces obliczania działania hamiltonianu przebiega w kilku krokach:

• Lokalny potencjał w przestrzeni rzeczywistej wymaga FFT, $O(n_v \ln n_v)$
• Projekcja może wystąpić w czasie rzeczywistym lub g przestrzeni, lub O ( n n s N V ) , odpowiednio$O(n_a n_p)$$O(n_a n_p n_v)$
• Potencjał nielokalny jest albo ukośne lub blokować przekątnej, lub O ( n o n 2 s ) , odpowiednio$O(n_a n_p)$$O(n_a n_p^2)$

wszystko to musi się zdarzyć raz na elektron (tak naprawdę funkcja falowa), więc dodaj współczynnik $n_e$ .

Za pomocą pewnych środków (np. Gram-Schmidt) funkcje falowe (funkcje własne hamiltonianu) muszą być utrzymywane prostopadle względem siebie, $O(n_e^2 n_v)$

Wreszcie, funkcje falowe muszą zostać złożone w gęstość elektronową. W przypadku kodów PW dokonuje się tego za pomocą jednej ostatniej FFT na funkcję fali (i sumy), $O(n_e n_v \ln n_v)$ .

Należy zauważyć, że wcześniej umieścić w kilku różnych „s N v odnosi się do objętości (rzeczywiście, jest to wielkość masy), n p jest liczbą reflektorów na atomie N jest ilość węgla, n e liczby elektronów. Formalnie n v , n a i n e są ze sobą liniowo powiązane ( n $n$$n_v$$n_p$$n_a$$n_e$$n_v$$n_a$$n_e$$n_p$ jest małą liczbą całkowitą), ale można sobie wyobrazić zwiększenie objętości o ustaloną liczbę elektronów (dodanie próżni w geometrii płyty / drutu) lub zwiększenie liczby projektorów o stałej liczbie atomów i elektronów (przy użyciu dokładniejszego pseudo-potencjału).

Często zdarza się, że problemy są ograniczone przez FFT, w którym to przypadku są skutecznie $O(n^2 \ln n)$