Crystal Structure Prediction via Oblivious Local Search

Dmytro Antypov, Argyrios Deligkas, Vladimir V. Gusev, Matthew J. Rosseinsky, Paul G. Spirakis, Michail Theofilatos

Abstract

We study Crystal Structure Prediction (CSP), one of the major problems in computational chemistry. This is essentially a continuous optimization problem, where many different, simple and sophisticated, methods have been proposed and applied. The simple searching techniques are easy to understand and implement but can be slow in practice. Conversely, sophisticated approaches perform well but often require a large number of parameters and chemical expertise for fine-tuning, which can introduce bias toward previously-known structures. Our contribution is twofold: we formalize the CSP problem from a theoretical computer science perspective and propose an "oblivious" local search algorithm. Our algorithm requires minimal knowledge about the composition and can be used as an intermediate step by any method. Experiments show that our approach outperforms standard basin hopping, a well-studied algorithm for this problem.

Introduction

Predicting how atoms will arrange themselves into a stable crystal—Crystal Structure Prediction (CSP)—is considered a "holy grail" of computational chemistry. Successfully predicting a structure from a chemical formula alone (e.g., $SrTiO_3$) enables the discovery of materials with revolutionary properties before laboratory synthesis.

However, CSP presents a significant optimization challenge. The "Potential Energy Surface" (PES) is highly non-convex, featuring an exponential number of local minima. Existing methods typically fall into two camps: simple random sampling, which is slow, and sophisticated evolutionary algorithms, which require expert tuning. This human intervention often introduces bias, steering searches toward familiar structures. This research introduces an "oblivious" approach that operates efficiently without needing deep chemical priors or complex parameter tuning.

Methodology

The authors treat energy calculation and structural relaxation (letting atoms settle into a local minimum) as black-box oracles. Their core contribution lies in the formalization of CSP and the introduction of novel search heuristics:

  • Formalization: CSP and its sub-problems are defined in rigorous Computer Science terms to facilitate future complexity analysis.
  • Depth Energy Computation: A combinatorial method estimates a crystal's energy by examining $k$ layers of surrounding unit cells. Even at low depths ($k=1$), this method accurately preserves the relative ranking of different structures.
  • The "Axes" Neighborhood: Instead of random movements, the algorithm moves ions along three axes parallel to the unit cell's facets. This acts as a high-speed filter to find better starting points for computationally expensive relaxations.
Visualization of a crystal unit cell (a) and its corresponding supercell (b) used in structural analysis.

Experimental Evaluation

The researchers evaluated their algorithms using two benchmark compositions:

  1. Strontium Titanate ($SrTiO_3$): This was used to test energy approximation accuracy. The "depth energy" method achieved an error of only 0.0032 eV at a depth of $k=6$ compared to industry standards. The "Axes" search was significantly faster at finding the global minimum than standard Basin Hopping.
  2. Yttrium Titanate ($Y_2Ti_2O_7$): A more complex structure with 22 atoms in the primitive unit cell. While standard Basin Hopping failed to find the optimal configuration after 3,500 trials, the oblivious algorithm found it after visiting only 720 structures.

Conclusion

By designing an algorithm that does not rely on chemical "building blocks" or expert-tuned parameters, the search remains unbiased, increasing the likelihood of discovering novel, counter-intuitive materials. The realization that energy approximations only need to be monotonic (preserving ranking) rather than perfectly precise allows for high-speed combinatorial filtering. Future work will focus on providing theoretical bounds for CSP and extending these oblivious search techniques to non-ionic crystals, such as covalent or metallic systems.

Summary updated

Abstract

We study Crystal Structure Prediction, one of the major problems in computational chemistry. This is essentially a continuous optimization problem, where many different, simple and sophisticated, methods have been proposed and applied. The simple searching techniques are easy to understand, usually easy to implement, but they can be slow in practice. On the other hand, the more sophisticated approaches perform well in general, however almost all of them have a large number of parameters that require fine tuning and, in the majority of the cases, chemical expertise is needed in order to properly set them up. In addition, due to the chemical expertise involved in the parameter-tuning, these approaches can be {\em biased} towards previously-known crystal structures. Our contribution is twofold. Firstly, we formalize the Crystal Structure Prediction problem, alongside several other intermediate problems, from a theoretical computer science perspective. Secondly, we propose an oblivious algorithm for Crystal Structure Prediction that is based on local search. Oblivious means that our algorithm requires minimal knowledge about the composition we are trying to compute a crystal structure for. In addition, our algorithm can be used as an intermediate step by {\em any} method. Our experiments show that our algorithms outperform the standard basin hopping, a well studied algorithm for the problem.
BibTeX
@inproceedings{antypov2020crystal,
  author = {Dmytro Antypov and Argyrios Deligkas and Vladimir V. Gusev and Matthew J. Rosseinsky and Paul G. Spirakis and Michail Theofilatos},
  title = {{Crystal Structure Prediction via Oblivious Local Search}},
  booktitle = {SEA},
  year = {2020},
  doi = {10.4230/lipics.sea.2020.21},
}
Figure