Finding well-optimized special quasirandom structures with decision diagram

The advanced data structure of the zero-suppressed binary decision diagram (ZDD) enables us to efficiently enumerate nonequivalent substitutional structures. Not only can the ZDD store a vast number of structures in a compressed manner, but also a set of structures satisfying given constraints can be extracted from the ZDD efficiently. Here, we present a ZDD-based efficient algorithm for exhaustively searching for special quasirandom structures (SQSs) that mimic the perfectly random substitutional structure. We demonstrate that the current approach can extract only a tiny number of SQSs from a ZDD composed of many substitutional structures ($>{10}^{12}$). As a result, we find SQSs that are optimized better than those proposed in the literature. A series of SQSs should be helpful for estimating the properties of substitutional solid solutions. Furthermore, the present ZDD-based algorithm should be useful for applying the ZDD to the other structure enumeration problems.

Figure 1

Illustration of two-dimensional derivative structure and pair clusters. (a) Primitive cell with basis vectors $\mathbf{A}$ and a set of point coordinates in the primitive cell, $D$. The shaded area represents the primitive cell. (b) Supercell derived from the primitive cell in (a). The index of its transformation matrix $\mathbf{M}$ is six, and there are six sites in the supercell, $D_{\mathbf{M}}=\{{\mathbf{d}}_1,{\mathbf{d}}_2,{\mathbf{d}}_3,{\mathbf{d}}_4,{\mathbf{d}}_5,{\mathbf{d}}_6\}$. (c) Binary derivative structure with the supercell in (b). When integers 0 and 1 represent the blue and yellow atoms, respectively, the reduced labeling $\mathbf{c}=(0,0,1,0,1,1)$ indicates that the blue atoms occupy sites ${\mathbf{d}}_1$, ${\mathbf{d}}_2$, and ${\mathbf{d}}_4$, and that the yellow ones occupy the other sites ${\mathbf{d}}_3$, ${\mathbf{d}}_5$, and ${\mathbf{d}}_6$. (d) Pair cluster $\alpha =\{{\mathbf{d}}_1,{\mathbf{d}}_2\}$ corresponding to the nearest-neighbor pair and its symmetrically equivalent pair clusters $\left[\alpha \right]$, represented by the red arrows. In the supercell in (b), there are $\left|\right[\alpha \left]\right|=12$ pair clusters equivalent to $\alpha$ due to the symmetry of the primitive cell.

Figure 2

Schematic diagram of the searching policy of SQSs in this paper. The definitions of these sets are given in Sec. 3.

Figure 3

Binary decision tree and its ZDD. The solid and broken arrows indicate 1-edge and 0-edge, respectively. The square boxes with 1 and 0 indicate 1-terminal and 0-terminal nodes, respectively. (a) Binary decision tree representing the family of subsets $\left\{\right\{a,b\},\{a,c\},\{b,c\left\}\right\}$. (b) ZDD of the binary decision tree derived by the reduction rules.

Figure 4

ZDDs of the two-dimensional example shown in Fig. 1. The nonterminal node $c_i$ corresponds to the occupation number of atom type 2 at site $i$ in the supercell. (a) ZDD representing reduced labelings of the two-dimensional example with equiatomic composition ${\mathcal{C}}_{\mathrm{conc}}$, which chooses three 1-edges from $c_1,\cdots ,c_6$. (b) ZDD representing feasible reduced labelings with equiatomic composition ${\mathcal{C}}_{\mathrm{feasible}}$. (c) ZDD representing SQSs up to the first NN pair cluster, ${\mathcal{C}}_{\mathrm{SQS}}^{N_c=1}$. (d) ZDD representing nonequivalent reduced labelings ${\mathcal{C}}_{\mathrm{sym}}$.

Figure 5

Development of a ZDD for ${\mathrm{\Pi }}_{{\alpha }_1}\left(\mathbf{c}\right)={\overline{\mathrm{\Pi }}}_{{\alpha }_1}=1/4$ of the two-dimensional example. A partially determined value of the correlation function ${\mathrm{\Pi }}_{{\alpha }_1}\left(\mathbf{c}\right)$ is attached to each edge from nonterminal nodes. An edge with “skipped” goes to the 0-terminal node because the corresponding labeling is not a feasible labeling.

Figure 6

Crystal structure of a binary fcc-based SQS-40 of $AB$. The orange and blue balls represent atom types $A$ and $B$, respectively. The tilted cube with the dotted lines indicates a conventional fcc unit cell.

Figure 7

Computational times to search for equiatomic fcc-based SQSs with the present ZDD-based method and the previous enumeration method on a logarithmic scale. The blue open and closed circles stand for the runtimes for constructing ZDDs for binary and ternary systems, respectively. The orange open and closed squares stand for the runtimes for naively searching for SQSs with the previous method. The horizontal axis indicates the index of the supercell.

Figure 8

Formation energies of SQSs. The horizontal axis indicates the number of sites in SQSs. The top figure shows the results for fcc random structures. The blue circles, orange up triangles, green down triangles, and red squares indicate ${\mathrm{Cu}}_{0.5}{\mathrm{Au}}_{0.5}$, ${\mathrm{Cu}}_{0.5}{\mathrm{Pd}}_{0.5}$, ${\mathrm{Pd}}_{0.5}{\mathrm{Au}}_{0.5}$, and ${\mathrm{Cu}}_{0.33}{\mathrm{Pd}}_{0.33}{\mathrm{Au}}_{0.33}$, respectively. The bottom figure shows the results for hcp random structures. The blue circles, orange up triangles, green down triangles, and red squares indicate ${\mathrm{Hf}}_{0.5}{\mathrm{Ti}}_{0.5}$, ${\mathrm{Hf}}_{0.5}{\mathrm{Zr}}_{0.5}$, ${\mathrm{Zr}}_{0.5}{\mathrm{Ti}}_{0.5}$, and ${\mathrm{Hf}}_{0.33}{\mathrm{Zr}}_{0.33}{\mathrm{Ti}}_{0.33}$, respectively.