Timeline for What is the computational scaling of DFT energy vs gradient vs Hessian?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 11 at 16:25 | comment | added | Nike Dattani - No Free Time | The big-O notation by definition hides the prefactor. O(N^p) = O(k*N^p) for any pre-factor k. Also, if the number of atoms M is constant, then O(N^p) = O(N^p M^q), so O(N^p) = O(N^3) is the answer for energies, gradients, and Hessians (modulo the adjustments discussed in the first link in my answer). Since this question asked for the answer in O(N^p) form, then a question about the pre-factor hidden under the big-O, would be most appropriate in a new post. There you can also specify that you want analytic derivatives instead of numerical ones, and perhaps also you want O(N^p M^q). | |
| Jul 11 at 16:19 | comment | added | Nike Dattani - No Free Time | You say that it's trivial to get the scaling for numerical derivatives, but it's far more trivial to get the scaling for DFT energies, as the screenshot of the Google search in my answer demonstrates. If one is asking for the answer to provide the scaling for DFT energies and gradients, then I don't think it's unreasonable for the answer to provide the scaling for numerical gradients, especially when we are asked for O(N^p) scaling, since N for DFT energies is usually the number of electrons, independent of the number of atoms, so the O(N^p) cost is the same for analytic/numerical derivatives. | |
| Jul 11 at 14:31 | comment | added | S R Maiti | Also I thought that it would be clear I was asking about analytic gradients because numeric ones are simply repeating the same calculation so it would be trivial to get the scaling. Maybe we are talking past each other - but I don't think what you wrote really answers my question. | |
| Jul 11 at 14:25 | comment | added | S R Maiti | I mean I wanted to know the scaling specifically to compare timings as I wrote in my question - I mentioned the big O notation because that's how I see these things represented in papers - if they exclude the pre-factor by definition then its not what I want. But do you know any references about the differences in pre-factor between energy, gradient and Hessian? | |
| Jul 10 at 21:41 | comment | added | Nike Dattani - No Free Time | @wzkchem5 Most people would use fewer basis functions for H than for "first row" elements such as C, N, O, etc., and would use more basis functions for transition metal elements, and even more for lanthanides and actinides. You are correct that if N is the number of basis functions/atom, the cost would be O(N^3 M^4) if the cost per basis function is O(N^3). In my last comment, I made an error when I wrote "N=10 basis functions per atom", because I always meant that N is the number of total basis functions. All of the subsequent analysis in that comment was based on N being the total. | |
| Jul 10 at 18:14 | comment | added | wzkchem5 | @NikeDattani-NoFreeTime It's a good point that not everyone intends to hold the basis size per atom fixed. But the cost is only $O(N^3M)$ when $N$ stands for the total number of basis functions. If $N$ stands for the number of basis functions per atom, then the cost would be $O(N^3M^4)$. | |
| Jul 10 at 12:53 | comment | added | Nike Dattani - No Free Time | @wzkchem5 The question did not say that the basis size per atom is held fixed, and more often than not, it is not held fixed. Anyway, if we assume that there's N=10 basis functions per atom and that the cost per basis function is N^3 (this would be somewhat true if N were the number of electrons rather than basis functions), then for M atoms we have a cost of (10M)^3 for energies. If we want numerical derivatives wrt the XYZ coordinates of M atoms, then we can repeat the calculation 3M times and get a cost of 3000M^4 = O(M^4) when really the cost is O(N^3*M) which is very different. | |
| Jul 10 at 12:11 | comment | added | Nike Dattani - No Free Time | Once someone has answered a question, changes to the question will almost always be rolled back. Your question didn't say whether you want analytic or numerical or automatic derivatives, so I gave an answer for all three. If you only wanted me to focus on analytic derivatives, it would have been better if that was made clear in the original question. Also, in your last comment you said that you want the pre-factor. But your question said you wanted the answer in big O notation, which by definition hides the pre-factor under the big O. A new post can ask for the pre-factor. | |
| Jul 9 at 19:28 | comment | added | wzkchem5 | @NikeDattani-NoFreeTime That's why I said "when the basis set size per atom is held fixed". Obviously the whole quantum chemistry community does not assume $M$ scales linearly with $N$, but if the basis set size per atom is held fixed, then $M$ has to scale linearly with $N$! But you are right that I shouldn't have said "assume" - it's a necessary conclusion, not an assumption. | |
| Jul 9 at 14:44 | comment | added | S R Maiti | I have to agree with wzchem5, I want to know the total power including the pre-factor of N (considering the same basis set but different number of atoms). Maybe the question was not clear - I will edit it. | |
| Jul 8 at 0:46 | comment | added | Nike Dattani - No Free Time | @wzkchem5 I don't think it's fair to say that the whole quantum chemistry community assumes that M scales linearly with N, because so much work is on dinuclear, trinuclear, and other small polynuclear molecules. I think the biggest molecule in the GW100 dataset has 16 nuclei, and the enormous GMTKN30 dataset which is composed of many smaller and widely used datasets, also doesn't have very big molecules. Even if M=500, if we assume that they are all carbon, then we have N=3000 electrons (linear scaling but with a prefactor of 6). I'm curious to see any reference that combines M and N! | |
| Jul 7 at 18:18 | comment | added | wzkchem5 | In my answer the definition of $M$ is the same as in your post. Now I understand you may mean the power of $N$, not the total power of $M$ and $N$. I was in the mindset of the quantum chemistry community, where (when the basis set size per atom is held fixed) it is assumed that $M$ scales linearly with $N$ and one tends to talk about their total power. | |
| Jul 7 at 17:43 | comment | added | Nike Dattani - No Free Time | @wzkchem5 what is M? In my answer it was the number of nuclear coordinates, in which case the scaling with respect to N is still the same whether you are calculating energies, gradients or Hessians. | |
| Jul 7 at 12:32 | comment | added | wzkchem5 | For analytic gradients, I agree, but for analytic Hessians the scaling (without using low order scaling tricks) is $O(N^pM)$, because one has to solve a CPHF equation with $O(M)$ right hand side (RHS) vectors. Solving the CPHF equation for a constant number of RHS vectors scales the same as SCF itself, but it also scales linearly with the number of RHS vectors. With complicated tricks it is possible to get rid of the $M$ factor (see doi.org/10.1063/1.4908131), but this usually requires $p$ to be first reduced to 1 or 2 from the original value of 3, which is already complicated. | |
| Jul 7 at 11:24 | history | edited | Nike Dattani - No Free Time | CC BY-SA 4.0 |
added 513 characters in body
|
| Jul 7 at 11:18 | history | answered | Nike Dattani - No Free Time | CC BY-SA 4.0 |