77

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 ...


22

To complement mykd's already excellent answer, I will just add that the approximant we all learn in school (the Taylor approximant) is nice to teach and easy to help students learn the concept of approximations, but in practice it's one of the worst options in terms of it's accuracy-to-complexity ratio. The Taylor approximant matches the $n^{\textrm{th}}$ ...


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 ...


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, ...


16

Great question! Protein folding has been in open question for decades. Just recently, there's been a lot of discussion regarding DeepMind's AlphaFold project, which was discussed at length on our very own site here. My answer will be complementary to the one above, but the references I will provide will be closer to the physics side of the problem. First ...


16

PADE refers to the mathematician Henri Padé, who developed the Padé approximation, which can approximate a function using rational polynomial functions. For ex: $$ \sin(x)\approx {\frac {(12671/4363920)x^{5}-(2363/18183)x^{3}+x}{1+(445/12122)x^{2}+(601/872784)x^{4}+(121/16662240)x^{6}}} $$ This feature is used to approximate the total correlational ...


15

In the paper "A Continued-Fraction Representation of the Time-Correlation Functions", generalized susceptibilities and transport coefficients for materials are obtained using a continued-fraction expansion of the Laplace transform of the time-correlation functions. This was the precursor to what is now called the "hierarchical equations of ...


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. ...


14

The question is too broad to be answered directly so I will provide a somewhat general scheme. Basically in an integral like $$ \int d\mu A B C $$ one would seek to expand each part in irreducible representations of a given group, say for instance \begin{align} B=\frac{1}{\vert \mathbf{r}-\mathbf{r}^\prime\vert} =\frac{1}{r} \sum_{\ell} \left(\frac{r'}{r}\...


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:...


13

This is a question that is answered by a straightforward literature search, here's e.g. two review papers from the 1980s: J. Chem. Inf. Comput. Sci. 25, 334 (1985) J. Chem. Educ. 65, 574 (1988) as well as a more recent encyclopedia article Encyclopedia of Computational Chemistry 1998, pp. 1169-1190


13

You may take a look at the Method of Continued Fractions used in quantum scattering theory—this was only formed in 19831 so is rather recent. Related is the PhD thesis by Kónya (2000)2; §3.3 onwards. Reference [1] Horáček, J., Sasakawa, T. (1983). Method of continued fractions with application to atomic physics. Physical Review A. 28(4):2151–2156....


12

I could list the models that could be used for microstructural modeling as: Phase-Field: It is constructed based on non-equilibrium thermodynamics and Onsager reciprocal relations to derive a functional for Gibbs free energy and then find the order variables (i.e. phase-field variable to describe the fraction of phases, concentration, temperature, stresses, ...


11

I'd just briefly add that among other things, chemical graph theory is extensively used for computing so-called "molecular descriptors", which are used to capture some "common properties" of a certain class of molecules. Todescini and Consonni, Molecular Descriptors for Chemoinformatics already a bit dated, offers an extensive collection ...


10

Someone more familiar with the problem might have a better suggestion, but I recently came across Daniel B. Dix' notes on Mathematical Models of Protein Folding. This is not my field, so I won't guarantee correctness. However, to a layman at least, these notes seem well suited for someone with your background. The abstract reads We present an elementary ...


10

Seeing that this question has gathered attention but no replies, I will give it a stab. Note that I am not an expert on DFT or functional calculus, so take this with a grain of salt. As usual, suggestions to the post will be welcome! Using an approach I saw here, we can use a chain rule and obtain the following: $$\frac{\delta F[\rho(\boldsymbol{r})]}{\delta ...


10

Plasticity is still an actively researched area. The Ludwik-Hollomon equation is one model that is used for the strain-hardening region since it captures the convex shape of the curve using a power law: $$\sigma = K \epsilon^{n} \tag{1}$$ Here, $n$ is known as the strain hardening coefficient or strain hardening exponent. This equation only captures the ...


9

Some recent work that comes to my mind is generation and analysis of fullerenes done by Peter Schwerdtfeger's group and described for example in J. Comput. Chem. 34 1508 (2013) WIREs 5, 96 (2015)


9

First, you have to transform all the basis functions into the irreducible representations (irreps) of the point group of the molecule. You can do this with standard projection formulas. Once, you know the irreps of the basis functions, you have to look at the product table of the point group to find out whether the product of those four basis functions ...


9

Too many references for me to elaborate on, but here's a recent example I like: "Graph Networks as a Universal Machine Learning Framework for Molecules and Crystals" in Chemistry of Materials.


9

The Davidson-Method is the best algorithm when you want a comparatively small number of eigenvectors/eigenvalues from a sparse, diagonally dominant matrix. MKL doesn’t have a sparse matrix diagonalization method, but it’s a good idea to use it for the Linear Algebra operations used when implementing Davidson. If you want ALL the eigenvectors then you ...


9

Following Nike Dattani's suggestion, I now add some comparisons of the Davidson method with methods that are more "modern" than it, to supplement the existing answers which compared the Davidson method with methods that predates it. However my answer will be more or less off-topic because I will mainly talk about disadvantages of the Davidson ...


9

By asking about the discretization of $\mathbf{r}$, I think you may be trying to visualize/intuitively understand the spatial variation of the energy and density, $\mathrm{d}E/\mathrm{d}\mathbf{r}$ and $\mathrm{d}n(\mathbf{r})/\mathrm{d}\mathbf{r}$, and you are conflating that with the meaning of the functional derivative $δE[n]/δn(\mathbf{r})$. If you have ...


9

You are developing the right idea, but your Eq. 1 is a bit awkward. To understand why, let me say a bit about functionals and functional derivatives. A functional acts on a function in its entirety, for example we need to know the full input function $n(r)$ in order to obtain the corresponding value for the functional: $$\tag{1} E[n(r)] = \int_0^1n(r)\textrm ...


9

NetworkX This is a widely-used Python library for graph theory stuff. Open source (https://github.com/networkx/networkx) under a 3-clause BSD license. Caveat: since this is a tool that knows nothing about chemistry, the "chemical" nature of the structure might get lost in the projection of the network (e.g., some bond lengths might not look ...


8

This paper might be a good example: Chem, 4, 390-398 (2018) Quoting the authors: 'Computer autonomously designs chemical syntheses of medicinally relevant molecules'.


8

The expression you are describing is equation (6) from your first link: $$R_j=\frac{3\hbar c\ln(10)1000}{16\pi^2N_A}\int_\text{band j}\frac{\Delta\epsilon}{\omega}d\omega\tag{1}$$ which defines the rotatory strength $R_j$ of a band $j$ as the differential absorption coefficient integrated over that band, with the units changed via a prefactor containing the ...


8

Recently chemical graph theory has been used to give more physical and chemical insight on whether destructive quantum interference exists or not. Hope that helps. Let me know if I can help further. Tsuji, Yuta, Ernesto Estrada, Ramis Movassagh, and Roald Hoffmann. "Quantum interference, graphs, walks, and polynomials." Chemical reviews 118, no. 10 ...


8

In the Huckel method, you are just generating a very simplified version of the molecular Hamiltonian and determining it's eigenvalues. The molecular Hamiltonian will always be a Hermitian matrix (for the Huckel method, we can be more specific and say it's a real symmetric matrix by construction). Hermitian matrices are guaranteed to have all real eigenvalues ...


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