Having shown that our compressed sensing procedure results in a 3\(\times\) speed-up for a moderately-sized organic molecule, we now move to larger systems and investigate how the cost of computing the Hessian scales with the number of atoms.  In the absence of compressed sensing, if the entries of the Hessian must be calculated independently, the cost of calculating the Hessian would scale as \(O(N^2) \times OE\), where \(OE\) is the cost of computing the energy of a given nuclear configuration (the cost of analytical and numerical derivatives usually have the same scaling). For example, for a DFT-based calculation, \(OE\) is typically \(O(N^3)\).  However, since many quantum mechanical methods obtain the Hessian one column at a time, only \(O(N)\) calculations are required, so the scaling is improved to \(O(N)\times OE\).

How does compressed sensing alter this scaling?  From eq.~\ref{eq:csscaling}, the number of matrix elements needed to recover the Hessian via compressed sensing scales as \(O(S \log N)\), where \(S\) is number of non-zero elements in the Hessian, so the net scaling is \(O(S \log N) \times OE\).  By obtaining the Hessian one column at a time, we expect the net scaling to improve to \(O(S/N \log N) \times OE\). However, we should note that eq.~\ref{eq:csscaling} is only valid in principle for the random sampling of elements, and it is not necessarily valid for a random column sampling. This scaling result illustrates the critical importance of recovering the Hessian in a sparse basis, with \(S\) as small as possible. So what is the smallest \(S\) that can reasonably be achieved?

For many large systems, the Hessian is already sparse directly in the basis of atomic Cartesian coordinates.  Since the elements of the Hessian are \emph{partial} second derivatives of the energy with respect to the positions of two atoms, only direct interactions between the two atoms, with the positions of all other atoms held fixed, must be taken into account.  For most systems we expect that this direct interaction has a finite range or decays strongly with distance.   Note that this does not preclude collective vibrational modes, which can emerge as a result of ``chaining together'' direct interactions between nearby atoms.

If we assume that a system has a finite range interaction between atoms, and since each atom has an approximately constant number of neighbors, irrespective of the total number of atoms in the molecule, the number of non-zero elements in a single column of the Hessian should be constant.  Hence, for large molecules, the sparsity \(S\) of the Hessian would scale linearly with the number of atoms \(N\).  Putting this result into \(O(S/N \log N) \times OE\) yields a best-case scaling of \(O\left(\log N \right)\times OE\), which is a significant improvement over the original \(O(N)\times OE\) in the absence of compressed sensing.

To study the validity of our scaling results we have performed numerical calculations on a series of polyacene molecules, which are aromatic compounds made of linearly fused benzene rings.  For polyacenes ranging from 1 to 15 rings, Fig.~\ref{fig:HessSparsity} illustrates the average number of non-zeros per column in the Hessian matrices obtained via molecular mechanics and quantum mechanical calculations in the basis of atomic coordinates.  In the molecular mechanics Hessians, the average sparsity per column approaches a constant value as the size of the polyacene increases, consistent with each atom having direct interaction with a constant number of other atoms.
