73

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


29

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


19

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


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

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

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


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


13

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


12

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

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


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

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

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


9

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


8

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)


8

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.


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

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


7

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


7

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


7

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


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


5

pyblock This simple Python code does a Flyvbjerg-Petersen blocking analysis on column(s) of data. It is also used in some larger softwae packages, such as NECI. You can run the code with the following command if you have just one column of data: python blocking.py -f180000 -d5 -o/ file.out where in this case 180000 is the line in file.out at which you want ...


5

I recommend you to visit and go through the COMSOL Multiphysics site. COMSOL software is based on finite element method (FEM) with applications in several areas of Physics. In the site, you can request a demonstration of the software (so you will have the experience to use FEM in practice) and also can visit the WEBMINARS section that is full of applications ...


5

Here is a short video tutorial to explain the following points about FEM: Why study FEM Engineering systems and FEM What is FEM? Layman's explanation Mathematical treatment The power of FEM Hope it helps.


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