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


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


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


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

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


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.


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

For this type of calculation, I find MATLAB/Octave to be easier, at least for demonstrating what to do. You can add the np. everywhere afterwards if you want to use Python. Assuming you have the following matrices already defined in your workspace: $\eta_z$ = eta $\tau_x$ = taux $\tau_y$ = tauy $\tau_z$ = tauz $m_z$ = tauz $\sigma_z$ = sigmaz, and the ...


8

It looks Doi makes some extra simplifications (beyond expanding the exponential) that are valid when the external field is weak. Let's start with what you wrote and make one simplification, $$ \begin{eqnarray} \overline{\delta \phi _a} &= \frac{\langle\delta \phi_a \rangle -\langle \delta \phi _a \beta U_{ext}\rangle}{\langle 1-\beta U_{ext}\rangle} \tag{...


7

Preamble Since I don't know your specific background, this is a generic answer for any applied mathematician wishing to enter the field of protein folding. Not everything will apply specifically to you, and please don't feel offended if there's something I assume you don't already know or do! First of all, as a fellow mathematician (I was trained in ...


7

There are two related structures. Dodecahedrane is known - $\ce{C20H20}$ in which the carbon atoms form the lattice you described, with hydrogen atoms on the outside. Beyond that, $\ce{C20}$, a fullerene is known, and you can find a great variety of similar structures, from $\ce{C20}$ to $\ce{C720}$. As for your discussion of quasi-crystals, I think it's ...


7

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


6

These PDEs are typical diffusion-drift PDEs that arise in a huge number of fields (including my field, which is electrochemistry) and are routinely solved using any numerical method of your choice, e.g. finite difference method and finite element method, in both open-source and commercial software. Nonlinearities are generally not an issue in my experience ...


6

The question is not very well-posed. However, the question appears to be about whether rotational invariance is honored by LCAO calculations. The old-time approach is to use Cartesian basis functions. Translating our origin to the nucleus, we can write the Cartesian basis functions in the form $\psi({\bf r}) = N x^k y^l z^m \exp(-\alpha r^2)$, where $\lambda:...


5

The continued fraction expansion is the most common way to calculate real-frequency dynamical Green's functions using Lanczos exact diagonalization. The method was introduced in this setting in Gagliano, E. R., and Balseiro, C. A., "Dynamical Properties of Quantum Many-Body Systems at Zero Temperature," Physical Review Letters 59, 2999 (1987), but ...


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