75

What are the state-of-the-art algorithms for long-integer multiplication? First let me address the point you raised about the schoolbook algorithm having $\mathcal{O}(n^2)$ scaling, by saying that this was not the state-of-the-art algorithm used in most matter modeling software. Below I give a brief overview: (1960) Karatsuba multiplication. $\mathcal{O}(n^{...


31

This $O(n\ln n)$ integer multiplication algorithm is a galactic algorithm, meaning that it won't be used despite being "of lower complexity" because it only becomes more efficient than existing algorithms for problems vastly larger than any relevant to us in practice. The problem is big-$O$ notation only tells us how the algorithm behaves for ...


27

2006 (Grimme): Double hybrid functionals The timeline of milestones you have given, includes a hybrid functional called B3LYP, which mixes a Hartree-Fock exchange functional with a GGA exchange-functional. In 2006, Stefan Grimme introduced what later became known as "double hybrid functionals", which not only mix the Hartree-Fock exchange functional with a ...


25

2015 (Sun et al.): SCAN functional The SCAN meta-GGA functional is an extension of the popular PBE GGA [1] and the TPSS [2] and revTPSS [3] meta-GGAs, SCAN adheres to all 17 known exact XC constraints and is constructed to be almost exact for the noble gasses and jellium surfaces. Early evidence suggests that SCAN is more accurate than and of comparable ...


24

This is a very broad question, so I am going to give a very brief overview of typical exponentially-scaling problems. I am not an expert in most of these areas, so any suggestions or improvements will be welcome. Solving the Schrödinger equation In order to solve the Schrödinger equation numerically, you need to diagonalise a rank $3N$ tensor -- as you can ...


21

To take a slight detour, we can also look at the progress of matrix multiplication algorithms. As mentioned in a few comments here, standard matrix multiplication is $O(n^{3})$ and any exact method for a general matrix is going to require $O(n^{2})$ operations just to process all the elements of initial matrices. Over the last 50 years, different methods ...


20

2013: Density-Corrected DFT (DC-DFT) The goal of Density-Corrected DFT (DC-DFT) is not only to get better accuracy but also to understand and correct the true error in the functional approximation.[1,2] In any approximate density functional, the DFT error is $\Delta E = \tilde E[\tilde n] - E[n]$ where $E$ and $n$ are exact functional and density while $\...


19

2004 (Yanai et al.): Range separation Often, the source of DFT improvement comes from Hartree-Fock as is also obvious from the answer involving double hybrid functionals. So too it is with range-separation. The electron-electron Coulomb operator for the exchange contribution is separated into a short and long range contribution. \begin{equation} \frac{1}{...


18

1993 (Becke): Hybrid Functionals Axel D. Becke introduced the adiabatic-connection model, which allows for mixing of DFT exchange and Fock-like exchange via the formula $$ E_{\text{x}} = a \cdot E^{\text{HF}}_x + b \cdot E^{\text{GGA}}_x $$ to obtain the exchange part of the exchange-correlation energy. Typically, one imposes $a+b = 1$, but some authors ...


17

1995 (Casida): TD-DFRT Time-Dependent Density Functional Response Theory is a linear response formulation of TDDFT for the calculation of excitation energies and corresponding transition amplitudes, that in turn allows to evaluate electronic spectra of molecular and condensed matter systems. The time-dependent density functional theory (TDDFT) in the Kohn–...


17

Can someone explain in detail the impact of any of the multiplication algorithms scaling better than N2, for some practical application? An actual application is right in front of our eyes: digital signature using RSA. If I click on the lock icon for the present page in my browser, then on the arrow on the right of Connection secure, then More Information, ...


15

Even the simplest better-than-schoolbook (O(n^2)) algorithms like Karatsuba are only useful in practice for large n. But what is n? It's not single bits, and it's not decimal digits. (Posting this tangent as requested in comments.) Software implementations of an extended-precision multiply algorithm work in integer chunks as wide as the hardware provides. ...


13

2005 (Bartlett): ab initio DFT Basically one takes the xc functional from a wave function approach such as MBPT(2), CC, etc. and constructs an xc potential from them using density conditions or a functional derivatives approach. Summary of developments is best captured in the following article: "Adventures in DFT by a wave function theorist." Details on ...


13

Practical importance: compactifying explanations It is widely believed that $\mathcal{O}(n \log n)$ is the best possible result, and therefore we no longer have to say $\mathcal{O}(n\log n\cdot 2^{2\log^*n})$ every single time in every single paper in related fields, we can just say $\mathcal{O}(n \log n)$ every time now. Here is a related quote from Reddit:...


12

The curse of dimensionality is indeed a huge problem in quantum chemistry, since the possible ways N electrons can occupy K orbitals is a binning problem whose computational cost grows factorially (almost as fast as x^x!) with the size of the system. Moreover, for accurate results you need K>>N in order to account for the so-called dynamical correlation, ...


11

I would add some developments in TDDFT that came around 1996 and resonated only later such as: the Casida equation (Casida 1995) that allows to calculate excitation energies and electronic spectra the real-time TDDFT (Yabana & Bertsch 1996) a non-perturbative TDDFT technique in which the time-dependent Kohn–Sham equation is solved by direct propagation ...


9

Most chemists' point of view could be condensed as follows: Implementation of DFT in Gaussian (Pople et al, 1992) LDAs and GGAs were implemented in Gaussian 92/DFT by Pople, Gill and Johnson [Chem Phys Lett 199, 557 (1992)]. DFT better than ab initio (Johnson et al, 1993) BLYP was found to yield more accurate equilibrium geometries, dipole moments, ...


9

From my experience with Stochastic Series Expansion (SSE) QMC (a type of discrete-time QMC) the computational cost scales like $\beta L^d$. In practice, it's often important to account for the finite-size gap $\Delta \propto 1/L$, so to stay consistently above or below that finite-size gap, $\beta$ is typically set to scale as $\beta = cL$, where $c$ is some ...


7

Conventional implementations of Kohn-Sham DFT scale cubically with system size. This is principally because at some point they: orthonormalise a set of $N$ trial states, each expressed in a basis comprising $M$ basis states; this has a computational cost $O(MN^2)+O(N^3)$ diagonalise a dense Hamiltonian matrix in the subspace of $N$ trial states, which has ...


7

2020 Furness et al: r$^2$SCAN functional The SCAN functional is the most recent meta-GGA functional constructed from first principles, which satisfies all known bounds. However, SCAN is also numerically pathological: getting converged energies requires huge quadrature grids, and constructing pseudopotentials is difficult. This motivated the construction of ...


7

1997 (Marzari & Vanderbilt): MLWF These methods enable a more qualitative view of the electron density by projecting the Bloch wavefunctions into localized Wannier functions [1], which is especially useful when it comes to transition metal systems, but not limited to these. This description enables DFT practitioners to "talk" to the modelling ...


6

2001 (Taylor et al.): DFT+NEGF Combining density functional theory (NEGF) with nonequilibrium Green's function method (NEGF), a self-consistent first-principles technique for modeling quantum transport properties of atomic and molecular scale nanoelectronic devices under external bias potentials is reported. Implementation packages: QuantumATK, Nanodcal ...


5

2014 (Gagliardi): MPCDFT Multiconfiguration Pair-Density Functional Theory (MC-PDFT) is a theoretical framework that combines multiconfigurational wave functions with a generalization of density functional theory. As the reference wavefunction is multiconfigurational rather than being a single Slater determinant, it has the advantage that it can describe ...


5

I have no prior experience with molecular dynamics really, but to get you started I have found a resource with a pretty detailed method of calculating the MSD (Mean square displacement). Looking at your plot, I suspect that periodic boundary conditions are somehow causing you a problem. It looks like it converges to a value that happens when everything ...


4

Alright, so it turns out @TristanMaxson was right - it was the periodic boundary conditions that were messing with my computation. The solution to it was to find the unwrapped coordinates of my system. This is how I unwrapped my coordinates: unwrapped_positions = relevant_positions.copy() for ts in range(0,n_time_points-1): periodic_displacement = \ ...


3

As the comments to your question suggest, there isn't a simple answer as there are many issues involved like system size, numerical tricks, hardware configuration, etc. There is an specific project that it is being developed at National Institute of Standards and Technology (NIST) under the name of DFT Benchmarking. The major accomplishments of the project ...


3

Solving the band-gap problem at DFT level (2008) To obtain the correct band-gap in semiconductor physics and materials science is very important for device applications, such as charge transport and optical absorption. It is well known that DFT with PBE exchange-correlation functional will underestimate the band-gap of semiconducting materials. Currently, ...


2

2016: Reproducibility of DFT calculations (Lejaeghere et al) Lejaeghere et al.$^1$ compared the calculated values for the equation of states for 71 elemental crystals from 15 different widely used DFT codes employing 40 different potentials. They defined a single parameter, Δ, which allowed the comparison of EOS calculated with different codes, giving a ...


Only top voted, non community-wiki answers of a minimum length are eligible