Accelerated enumeration of derivative structures using zero-suppressed binary decision diagram

The enumeration of “derivative structures” [1], which are unique substitutional atomic configurations derived from a given parent lattice, plays an essential role in searching for the ground states in multi-component systems. The possible size of supercells to enumerate the derivative structures, however, is limited because the number of the derivative structures increases exponentially as the number of sites in a substitutional lattice increases. In the present study, we apply a compressed data structure of the zero-suppressed binary decision diagram (ZDD) [2] to enumerate the derivative structures much more efficiently. We also employ an efficient procedure [3] to build the ZDD representing the derivative structures without listing all substitutional structures. The present study shows simple applications of the procedure to enumerate the derivative structures for the face-centered cubic and hexagonal close-packed parent lattices in binary, ternary, and quaternary systems. The present procedure with the ZDD should significantly contribute to computational approaches based on the derivative structures.
[1] G. L. W. Hart and R. W. Forcade, Phys. Rev. B 77, 224115 (2008).
[2] S. Minato, DAC ’93 (1993).
[3] T. Horiyama, et al., CCCG (2018).