9
$\begingroup$

Big O notation is commonly seen in the papers on novel computational methods. However, only a few of them include rigorous analysis of the algorithm. Is there any literature that summarizes current prevalent computational chemistry algorithm of density functional theory, coupled cluster, density matrix renormalization group and quantum monte carlo and gives analysis of their big O notations?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ DFT costs $N^3$, CC cost depends on the order of the CC expansion, but is easy to find, and the cost of DMRG is summarized in section 4.6 of this. In each of these cases, the cost analysis is maybe enough for an end-of-term project for a senior-level undergrad course, but is not enough to justify publication in a scientific journal. Your use of the word "etc." also makes this question very open-ended. Perhaps you should ask for the cost of the specific algorithms you're interested in, because there likely is no paper that has what you want. $\endgroup$
    – Nike Dattani - No Free Time
    Commented May 27, 2020 at 4:24
  • 1
    $\begingroup$ @NikeDattani I agree this is a very open question. However, I think this problem is non-trival. For example the statement that DFT is O(N^3) is imprudent. I think the details matters. There are many variation or ramification of the same method. Like in DFT, there are many tricks on diagonalizatin and constructions for integrals. I think people should be more systematic or even build a data base that classify and summarize each algorithm. $\endgroup$
    – Paulie Bao
    Commented May 27, 2020 at 4:56
  • 1
    $\begingroup$ I have specified the question a little. I hope this would work. $\endgroup$
    – Paulie Bao
    Commented May 27, 2020 at 5:58
  • 2
    $\begingroup$ I think this is a great question. In fact, this comment chain demonstrates that. Addressing @Nike Dattani's comment, rarely in practice does DFT actually scale as $N^3$. A great answer is discussed here. I agree that it would be nice to see similar analysis/discussion but with actual references and/or analysis to back it up. $\endgroup$
    – Andrew Rosen
    Commented May 27, 2020 at 15:47
  • 2
    $\begingroup$ It would be fun to answer this for the implementations not just the algorithms. Prefactors matter and different formalisms of the same method can have noticeably different costs. $\endgroup$
    – Jeff Hammond
    Commented May 28, 2020 at 3:54

0

Reset to default