Introduction
In solid-solid phase transition (SSPT), atoms in one crystal structure are rearranged to form another crystal structure. This process establishes an atom-to-atom correspondence between the initial and final structures, which is called a crystal-structure match (CSM) [1 , 2 , 3 ] . Every transition path on the potential energy surface (PES) determines a CSM, while the latter describes the SSPT more concisely and flexibly. Consequently, it is common for researchers to identify the CSM, rather than the transition path, to determine which SSPT mechanism is involved [4 , 5 , 6 , 7 , 8 ] . This is especially true in nucleation simulations [7 , 8 , 9 , 10 ] , where the term “mechanism” is almost synonymous with “CSM”, which serves as a common language for both nucleation and concerted mechanism studies [3 ] .
It has long been believed that SSPTs, like chemical reactions, occur along a minimum energy path (MEP) with the lowest energy barrier [11 , 12 , 13 ] . Just as each transition path determines a CSM, each CSM can also yield an MEP through methods such as the solid-state nudged elastic band (NEB) [12 ] . However, NEB-like methods can only produce an MEP with the user-specified CSM, ignoring all other CSMs and their MEPs, as illustrated in Figure 1 . Hence, despite their great success, NEB-like methods may still fail to give the lowest-barrier MEP, which has been an open question in the SSPT mechanism research for the past decade [13 , 14 , 15 ] . The main difficulty is that unlike the atom-to-atom correspondence in a chemical reaction, possible CSMs in an SSPT are extremely numerous—due to the large number of identical atoms and possible ways of lattice deformation—and thus hard to determine by human intuition [1 , 2 , 3 ] .
Figure 1. A schematic diagram showing that the initial structure (orthorhombic, yellow) may evolve to the final structure (hexagonal, other colors) in a number of ways. (a) After specifying the final structure as shown in the blue box, the NEB method can find the MEP denoted by the blue dashed line. However, to become the final structure, neither the lattice nor the atoms must end up as the blue box. Other possible endpoints spread out in both lattice and atomic degrees of freedom (DOF) on the PES, whose MEPs (gray dashed lines) are inaccessible. (b) Endpoints that differ in rigid transformations (cyan) can be easily taken into account by the NEB method [20 ] . (c) Endpoints that differ in CSMs, including those with the same SLM (pink) and different SLMs (purple), which we use CRYSTMATCH to exhaust.
To investigate what CSMs are favored by the SSPT, efforts have been made on two fronts: variable-CSM MEP calculation [14 , 15 ] and pure geometric CSM optimization [13 ] . The former includes the stochastic surface walking (SSW) [15 , 16 , 17 ] and PALLAS [14 ] , where intensive energy calculations hinder the enumeration of CSMs. The latter relies on a specific optimization criterion, such as minimum strain [18 ] , minimum number of broken bonds [1 ] , or minimum total distance traveled by the atoms [2 , 19 ] . However, geometrically optimized CSMs may not have the lowest energy barrier, and some are even suboptimal under their own criteria [3 ] . It would be useful to list all possible CSMs, both to guide MEP calculations and to identify the best CSM under any geometric criterion—yet, such a methodology is lacking.
In this paper, we present a complete classification of CSMs, and the CRYSTMATCH method for exhaustively enumerating them. To this end, a mathematical formalism is developed in Section II such that the deformation gradient, sublattice match (SLM), multiplicity and shuffle distance of a CSM can be rigorously defined in a cell-independent manner. These concepts organize all CSMs into a tree-like structure, as shown in Figure 2 , whose matrix representation and pruning scheme are discussed in Section III. To traverse this tree, three algorithms are detailed in Section IV. We demonstrate their application using the B1–B2 and graphite-to-diamond transitions as examples in Section V.
Figure 2. Given the initial and final crystal structures, all CSMs between them can be classified into a tree by their multiplicities and SLMs. Without restrictions, the tree would have infinite breadth at each level. For empirical (see Table II ) and computational considerations, an upper bound μ max \mu_{\max} μ m a x for the multiplicity μ \mu μ is introduced. Also, CSMs with too much strain or shuffle distance are deemed nonphysical. Under these prunings, the remaining tree contains only a finite number of CSMs, which can be obtained via Algorithms 1 and 2.
It should be noted that the molecular dynamics (MD) has also been used extensively to study SSPTs [21 ] . Among different transition paths, the one with the lowest energy barrier is most likely to be obtained by MD. This bypasses the CSM problem, but it takes an average time t ˉ ∝ exp ( β Δ ‡ ) \bar{t} \propto\exp(\beta\Delta^{\ddagger}) t ˉ ∝ exp ( β Δ ‡ ) to see a rare event with energy barrier Δ ‡ \Delta^{\ddagger} Δ ‡ to happen. Such Δ ‡ \Delta^{\ddagger} Δ ‡ increases linearly with the supercell volume until it can accommodate a critical nucleus [8 , 9 , 10 , 12 ] , making the MD simulation very hard—if not infeasible. Fortunately, enhanced sampling techniques like the metadynamics (MetaD) [22 , 23 ] can reinforce the occurrence of rare events by adding a history-dependent bias potential, making it possible to simulate nucleation in SSPTs [8 , 9 ] . Nevertheless, the bias potential may elevate different energy barriers unequally, thus altering the lowest-barrier path and CSM. We do not discuss here how CRYSTMATCH can serve MetaD, but simply show that the enumeration results of the former contain the CSM yielded by the latter.
Conventionally, CSMs are described by a pair of initial and final supercells, as shown in Figure 3 . However, the multivaluedness of this description causes severe in-
Figure 3. Four CSMs from A \mathcal{A} A (orthorhombic) to B \mathcal{B} B (hexagonal). Each CSM is described by the correspondences between the initial and final supercell vectors (pink), and two translational-inequivalent atoms (black). From the labels on the atoms (0–9 and A–F) in B \mathcal{B} B , one can see that J 1 = J 2 ≠ J 3 ≠ J 4 \mathcal{J}_1 = \mathcal{J}_2 \ne\mathcal{J}_3 \ne\mathcal{J}_4 J 1 = J 2 = J 3 = J 4 .
conveniences for both the theory and the enumeration of CSMs [2 , 3 , 24 ] . The purpose of this section is to establish a cell-independent formalism, making it self-evident that multiplicity and SLM—the main subjects in Figure 2 —are general, singlevalued, intrinsic properties of CSMs. We also define congruence relations among CSMs and SLMs, which are crucial for the efficiency of CRYSTMATCH.
To ensure the unambiguousness of the narration and proofs, we define fundamental terms (e.g., “lattice” and “crystal structure”) using the language of set theory. All lemmas are proved in Appendix A, while frequently used symbols are summarized in Table 1 . Commutative diagrams, as a tool for depicting the composition of homomorphisms, are also adopted to simplify the exposition. Let us begin with a set of points in R 3 \mathbb{R}^{3} R 3 , where each point is endowed with an atomic species; we denote by X \mathbb{X} X the set of all atomic species.
Table 1. TABLE I. Frequently used symbols in Section II.
Definition 1 (Atomic Structure). An atomic structure is a nonempty set A ⊂ R 3 \mathcal{A} \subset\mathbb{R}^{3} A ⊂ R 3 together with a mapping χ A : A → X \chi_{\mathcal{A}}:\mathcal{A}\to\mathbb{X} χ A : A → X .
Definition 2 (Atom-to-Atom Correspondence). Let A \mathcal{A} A and B \mathcal{B} B be atomic structures. We say that a mapping J : A → B \mathcal{J}:\mathcal{A}\to\mathcal{B} J : A → B is an atom-to-atom correspondence if (1) J \mathcal{J} J is bijective, and (2) J \mathcal{J} J preserves atom species, i.e., makes the following diagram commute:
A → J B χ A ↓ ↓ χ B X = X (1) \begin{CD}
\mathcal{A} @>\mathcal{J}>> \mathcal{B} \\
@V\chi_{\mathcal{A}}VV @VV\chi_{\mathcal{B}}V \\
\mathbb{X} @= \mathbb{X} \tag*{(1)}
\end{CD} A χ A ↓ ⏐ X J B ↓ ⏐ χ B X (1)
The above diagram is essentially a directed graph, whose vertices are sets and arrows are mappings. Paths composed of multiple arrows naturally represent a composite mapping, from its starting point to its endpoint. Commutativity of Eq. (1) means that any two paths with the same starting point and endpoint are equal, i.e.,
χ A = χ B ∘ J . (2) \chi_{\mathcal{A}}=\chi_{\mathcal{B}}\circ\mathcal{J}. \tag*{(2)} χ A = χ B ∘ J . (2)
One can also interpret Eq. (1) as follows: For any a ∈ A \mathbf{a}\in\mathcal{A} a ∈ A , it is mapped along different paths to
χ A ( a ) = χ B ( J ( a ) ) , (3) \chi_{\mathcal{A}}(\mathbf{a})=\chi_{\mathcal{B}}(\mathcal{J}(\mathbf{a})), \tag*{(3)} χ A ( a ) = χ B ( J ( a )) , (3)
which means that the species of atom a \mathbf{a} a is the same as that of its counterpart J ( a ) \mathcal{J}(\mathbf{a}) J ( a ) .
Commutative diagrams are primarily used in category theory and homological algebra, where the arrows represent homomorphisms. In this spirit, we redefine for all subsequent diagrams: Arrows between two atomic structures always represent atom-to-atom correspondences, i.e., species-preserving bijections. Consequently, the symbols χ A \chi_{\mathcal{A}} χ A and X \mathbb{X} X no longer appear in most diagrams. This approach handles polyatomic SSPTs once and for all. We hope the reader keeps in mind that A ⟶ B \mathcal{A}\longrightarrow\mathcal{B} A ⟶ B denotes an “isomorphism” between atomic structures.
Lattices and crystal structures
Definition 3 (Lattice). We say that a vector set L ⊂ R 3 L\subset\mathbb{R}^{3} L ⊂ R 3 is a lattice if it (1) is a group under vector addition, (2) is full rank (has three linearly independent elements), and (3) has a positive lower bound λ \lambda λ on the distance between any two of its elements, i.e.,
∀ t 1 , t 2 ∈ L , t 1 ≠ t 2 ⟹ ∣ t 1 − t 2 ∣ ≥ λ . (4) \forall\mathbf{t}_{1},\mathbf{t}_{2}\in L,\quad\mathbf{t}_{1}\ne\mathbf{t}_{2}\ \Longrightarrow\ \lvert\mathbf{t}_{1}-\mathbf{t}_{2}\rvert\ge\lambda. \tag*{(4)} ∀ t 1 , t 2 ∈ L , t 1 = t 2 ⟹ ∣ t 1 − t 2 ∣ ≥ λ . (4)
Definition 4 (Crystal Structure). Let A \mathcal{A} A be an atomic structure. We say that a vector t ∈ R 3 \mathbf{t}\in\mathbb{R}^{3} t ∈ R 3 is a translation element of A \mathcal{A} A if the mapping a ↦ a + t \mathbf{a}\mapsto\mathbf{a}+\mathbf{t} a ↦ a + t is an atom-to-atom correspondence from A \mathcal{A} A to itself, i.e.,
A → + t A . (5) \mathcal{A}\xrightarrow{+\mathbf{t}}\mathcal{A}. \tag*{(5)} A + t A . (5)
We say that an atomic structure A \mathcal{A} A is a crystal structure if all its translation elements form a lattice, denoted as L A L_{\mathcal{A}} L A . We refer to L A L_{\mathcal{A}} L A as the lattice of A \mathcal{A} A , and sublattices of L A L_{\mathcal{A}} L A sublattices of A \mathcal{A} A .
Let L ~ A \widetilde{L}_{\mathcal{A}} L A be a sublattice of a crystal structure A \mathcal{A} A . The relation ∼ \sim ∼ on A \mathcal{A} A defined as
a ∼ a ′ ⟺ ∃ t ∈ L ~ A , a ′ = a + t (6) \mathbf{a}\sim\mathbf{a}'\quad\Longleftrightarrow\quad\exists\mathbf{t}\in\widetilde{L}_{\mathcal{A}},\quad\mathbf{a}'=\mathbf{a}+\mathbf{t} \tag*{(6)} a ∼ a ′ ⟺ ∃ t ∈ L A , a ′ = a + t (6)
is an equivalence relation, whose reflexivity, symmetry, and transitivity are ensured by the identity element, invertibility, and closure of the group ( L ~ A , + ) (\widetilde{L}_{\mathcal{A}},+) ( L A , + ) , respectively. We say that a , a ′ ∈ A \mathbf{a},\mathbf{a}'\in\mathcal{A} a , a ′ ∈ A are L ~ A \widetilde{L}_{\mathcal{A}} L A -equivalent, and denote the L ~ A \widetilde{L}_{\mathcal{A}} L A -equivalence class of a \mathbf{a} a by
a + L ~ A = { a + t ∣ t ∈ L ~ A } , (7) \mathbf{a}+\widetilde{L}_{\mathcal{A}}=\left\{\mathbf{a}+\mathbf{t}\mid\mathbf{t}\in\widetilde{L}_{\mathcal{A}}\right\}, \tag*{(7)} a + L A = { a + t ∣ t ∈ L A } , (7)
and the quotient set by
A / L ~ A = { a + L ~ A ∣ a ∈ A } . (8) \mathcal{A}/\widetilde{L}_{\mathcal{A}}=\left\{\mathbf{a}+\widetilde{L}_{\mathcal{A}}\mid\mathbf{a}\in\mathcal{A}\right\}. \tag*{(8)} A / L A = { a + L A ∣ a ∈ A } . (8)
For any crystal structure A \mathcal{A} A , we denote Z A = ∣ A / L A ∣ Z_{\mathcal{A}}=\lvert\mathcal{A}/L_{\mathcal{A}}\rvert Z A = ∣ A / L A ∣ , which equals to the number of atoms in a primitive cell. Actual crystal structures all have a finite Z A Z_{\mathcal{A}} Z A since they have a finite atomic density. We will assume this henceforth, but the reader can also modify Definition 1 to make it rigorous; see Lemma 9.
Definition 5 (CSM). A crystal structure match (CSM) is an atom-to-atom correspondence between two crystal structures. We denote the set of all CSMs from crystal structure A \mathcal{A} A to crystal structure B \mathcal{B} B by CSM ( A , B ) \operatorname{CSM}(\mathcal{A},\mathcal{B}) CSM ( A , B ) .
Decomposing crystal-structure matches
Now we aim at defining the deformation gradient of a CSM. Our approach is to first define the shuffle , a type of CSM that is considered to have no deformation. Then, we will define the deformation of a general CSM as the difference between that CSM and a shuffle, as shown in Figure 4 (a). In the following text, the composition of mappings (including CSMs, linear transformations, and translations) will appear more frequently. When there is no risk of confusion, we will denote f ∘ g f \circ g f ∘ g simply as f g fg f g .
Figure 4. (a) An example of J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) being decomposed into a deformation gradient S ∈ CSM ( A , S A ) S\in\operatorname{CSM}(\mathcal{A},S\mathcal{A}) S ∈ CSM ( A , S A ) and a shuffle J S − 1 ∈ CSM ( S A , B ) \mathcal{J}S^{-1}\in\operatorname{CSM}(S\mathcal{A},\mathcal{B}) J S − 1 ∈ CSM ( S A , B ) . (b) In the above decomposition, a sublattice L ~ A ⊂ L A \widetilde{L}_{\mathcal{A}}\subset L_{\mathcal{A}} L A ⊂ L A is deformed to the shuffle lattice L ~ B ⊂ L B \widetilde{L}_{\mathcal{B}}\subset L_{\mathcal{B}} L B ⊂ L B . We call the triplet ( L ~ A , L ~ B , S ) (\widetilde{L}_{\mathcal{A}},\widetilde{L}_{\mathcal{B}},S) ( L A , L B , S ) the SLM of J \mathcal{J} J .
Definition 6 (Shuffle). Let A \mathcal{A} A and B \mathcal{B} B be crystal structures. We say that a vector t ∈ L A ∩ L B t \in L_{\mathcal{A}} \cap L_{\mathcal{B}} t ∈ L A ∩ L B is a translation element of J ∈ CSM ( A , B ) \mathcal{J} \in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) if we have the commutative diagram:
A → J B + t ↓ ↓ + t A → J B (9) \begin{CD}
\mathcal{A} @>\mathcal{J}>> \mathcal{B} \\
@V{+t}VV @VV{+t}V \\
\mathcal{A} @>\mathcal{J}>> \mathcal{B} \tag*{(9)}
\end{CD} A + t ↓ ⏐ A J J B ↓ ⏐ + t B (9)
i.e., J ( a + t ) = J ( a ) + t \mathcal{J}(a+t)=\mathcal{J}(a)+t J ( a + t ) = J ( a ) + t for all a ∈ A a\in\mathcal{A} a ∈ A . If all translation elements of J \mathcal{J} J form a lattice, we refer to it as the shuffle lattice of J \mathcal{J} J and say that J \mathcal{J} J is a shuffle. We use a squiggly arrow A ⇝ B \mathcal{A}\rightsquigarrow\mathcal{B} A ⇝ B to denote a shuffle.
In actual SSPTs, A \mathcal{A} A and B \mathcal{B} B in different phases generally have no common translation elements (except 0 \mathbf{0} 0 ), in which case J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) can never be a shuffle. However, it is possible to deform A \mathcal{A} A such that the deformed structure shares more translation elements with B \mathcal{B} B , making the deformed CSM a shuffle. To formalize this idea, we denote by S A = { S a ∣ a ∈ A } S\mathcal{A}=\{Sa\mid a\in\mathcal{A}\} S A = { S a ∣ a ∈ A } the crystal structure deformed from A \mathcal{A} A via S ∈ GL ( 3 , R ) S\in\operatorname{GL}(3,\mathbb{R}) S ∈ GL ( 3 , R ) . It has a canonical atom-species mapping χ A S − 1 \chi_{\mathcal{A}}^{S^{-1}} χ A S − 1 , which is the only mapping that makes the following diagram commutes:
A → S S A χ A ↓ ↓ χ A S − 1 X = X (10) \begin{CD}
\mathcal{A} @>S>> S\mathcal{A} \\
@V{\chi_{\mathcal{A}}}VV @VV{\chi_{\mathcal{A}}^{S^{-1}}}V \\
\mathcal{X} @= \mathcal{X} \tag*{(10)}
\end{CD} A χ A ↓ ⏐ X S S A ↓ ⏐ χ A S − 1 X (10)
thus making S ∈ CSM ( A , S A ) S\in\operatorname{CSM}(\mathcal{A},S\mathcal{A}) S ∈ CSM ( A , S A ) . Now we draw the commutative diagram corresponding to Figure 4 (a).
Definition 7 (Deformation Gradient). We say that S ∈ GL ( 3 , R ) S\in\operatorname{GL}(3,\mathbb{R}) S ∈ GL ( 3 , R ) is a deformation gradient of J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) if we have the commutative diagram:
A → J B S ↓ ↑ J S − 1 S A (11) \begin{CD}
\mathcal{A} @>\mathcal{J}>> \mathcal{B} \\
@V{S}VV @AA{\mathcal{J}S^{-1}}A \\
S\mathcal{A} \tag*{(11)}
\end{CD} A S ↓ ⏐ S A J B ⏐ ↑ J S − 1 (11)
i.e., J S − 1 : S A → B \mathcal{J}S^{-1}:S\mathcal{A}\to\mathcal{B} J S − 1 : S A → B is a shuffle.
Classifying crystal-structure matches
Next, we will show the uniqueness of the decomposition in Figure 4 (a). This makes the concept of SLM well-defined, which is crucial for classifying and representing CSMs, as shown in Figure 4 (b).
Theorem 1. The deformation gradient of a CSM is either unique or nonexistent.
Proof. Assume that J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) has two deformation gradients S 1 S_1 S 1 and S 2 S_2 S 2 . By Definition 7 we have the commutative diagram:
A → S 2 S 2 A S 1 ↓ ↓ J S 2 − 1 S 1 A → J S 1 − 1 B (12) \begin{CD}
\mathcal{A} @>S_2>> S_2\mathcal{A} \\
@V{S_1}VV @VV{\mathcal{J}S_2^{-1}}V \\
S_1\mathcal{A} @>>{\mathcal{J}S_1^{-1}}> \mathcal{B} \tag*{(12)}
\end{CD} A S 1 ↓ ⏐ S 1 A S 2 J S 1 − 1 S 2 A ↓ ⏐ J S 2 − 1 B (12)
We denote the shuffle lattices of J S 1 − 1 \mathcal{J}S_1^{-1} J S 1 − 1 and J S 2 − 1 \mathcal{J}S_2^{-1} J S 2 − 1 by L ~ 1 \widetilde{L}_1 L 1 and L ~ 2 \widetilde{L}_2 L 2 , respectively. For each t ∈ L ~ 1 ∩ L ~ 2 t\in\widetilde{L}_1\cap\widetilde{L}_2 t ∈ L 1 ∩ L 2 , we have the commutative diagram:
S 1 A → J S 1 − 1 B ← J S 2 − 1 S 2 A + t ↓ ↓ + t ↓ + t S 1 A → J S 1 − 1 B ← J S 2 − 1 S 2 A (13) \begin{CD}
S_1\mathcal{A} @>{\mathcal{J}S_1^{-1}}>> \mathcal{B} @<{\mathcal{J}S_2^{-1}}<< S_2\mathcal{A} \\
@V{+t}VV @VV{+t}V @VV{+t}V \\
S_1\mathcal{A} @>>{\mathcal{J}S_1^{-1}}> \mathcal{B} @<{\mathcal{J}S_2^{-1}}<< S_2\mathcal{A} \tag*{(13)}
\end{CD} S 1 A + t ↓ ⏐ S 1 A J S 1 − 1 J S 1 − 1 B ↓ ⏐ + t B J S 2 − 1 J S 2 − 1 S 2 A ↓ ⏐ + t S 2 A (13)
Combining Eqs. (12) and (13) , we obtain:
A → S 2 S 2 A S 1 ↓ ↑ J S 2 − 1 S 1 A → J S 1 − 1 B A → S 2 S 2 A S 1 ↓ ↑ J S 2 − 1 S 1 A → J S 1 − 1 B (14) \begin{CD}
\mathcal{A} @>S_2>> S_2\mathcal{A} \\
@V{S_1}VV @AA{\mathcal{J}S_2^{-1}}A \\
S_1\mathcal{A} @>>{\mathcal{J}S_1^{-1}}> \mathcal{B}
\end{CD}
\qquad
\begin{CD}
\mathcal{A} @>S_2>> S_2\mathcal{A} \\
@V{S_1}VV @AA{\mathcal{J}S_2^{-1}}A \\
S_1\mathcal{A} @>>{\mathcal{J}S_1^{-1}}> \mathcal{B} \tag*{(14)}
\end{CD} A S 1 ↓ ⏐ S 1 A S 2 J S 1 − 1 S 2 A ⏐ ↑ J S 2 − 1 B A S 1 ↓ ⏐ S 1 A S 2 J S 1 − 1 S 2 A ⏐ ↑ J S 2 − 1 B (14)
from which we can extract the subdiagram:
S 1 A → S 1 A → S 2 S 2 A + t ↓ ↓ + t S 1 A → S 1 A → S 2 S 2 A (15) \begin{CD}
S_{1}\mathcal{A} @>{S_{1}}>> \mathcal{A} @>{S_{2}}>> S_{2}\mathcal{A} \\
@V{+t}VV @. @VV{+t}V \\
S_{1}\mathcal{A} @>{S_{1}}>> \mathcal{A} @>{S_{2}}>> S_{2}\mathcal{A} \tag*{(15)}
\end{CD} S 1 A + t ↓ ⏐ S 1 A S 1 S 1 A A S 2 S 2 S 2 A ↓ ⏐ + t S 2 A (15)
The commutativity of Eq. (15) means that S 1 − 1 t = S 2 − 1 t S_{1}^{-1}t=S_{2}^{-1}t S 1 − 1 t = S 2 − 1 t . By Definitions 6, both L ~ 1 \widetilde{L}_{1} L 1 and L ~ 2 \widetilde{L}_{2} L 2 are sublattices of L B L_{B} L B so that L ~ 1 ∩ L ~ 2 \widetilde{L}_{1}\cap\widetilde{L}_{2} L 1 ∩ L 2 is full rank (Lemma 10). Hence, there exist three linearly independent vectors t 1 , t 2 , t 3 \mathbf{t}_{1},\mathbf{t}_{2},\mathbf{t}_{3} t 1 , t 2 , t 3 such that
S 1 − 1 [ t 1 , t 2 , t 3 ] = S 2 − 1 [ t 1 , t 2 , t 3 ] . (16) S_{1}^{-1}[\mathbf{t}_{1},\mathbf{t}_{2},\mathbf{t}_{3}]=S_{2}^{-1}[\mathbf{t}_{1},\mathbf{t}_{2},\mathbf{t}_{3}]. \tag*{(16)} S 1 − 1 [ t 1 , t 2 , t 3 ] = S 2 − 1 [ t 1 , t 2 , t 3 ] . (16)
Since [ t 1 , t 2 , t 3 ] [\mathbf{t}_{1},\mathbf{t}_{2},\mathbf{t}_{3}] [ t 1 , t 2 , t 3 ] is invertible, we have S 1 = S 2 S_{1}=S_{2} S 1 = S 2 . ■
Theorem 1 enables us to classify CSMs by their deformation and shuffle. Now, we merge the deformation gradient and the shuffle lattice into a single concept, whose utility will become evident in Sections III and IV.
Definition 8 (SLM). Let A \mathcal{A} A , B \mathcal{B} B be crystal structures, L ~ A \widetilde{L}_{A} L A , L ~ B \widetilde{L}_{B} L B their respective sublattices, and S ∈ GL ( 3 , R ) S\in\operatorname{GL}(3,\mathbb{R}) S ∈ GL ( 3 , R ) . We say that ( L ~ A , L ~ B , S ) (\widetilde{L}_{A},\widetilde{L}_{B},S) ( L A , L B , S ) is a sublattice match (SLM) from A \mathcal{A} A to B \mathcal{B} B if
∣ A / L ~ A ∣ = ∣ B / L ~ B ∣ , (17) |\mathcal{A}/\widetilde{L}_{A}|=|\mathcal{B}/\widetilde{L}_{B}|, \tag*{(17)} ∣ A / L A ∣ = ∣ B / L B ∣ , (17) S L A = L B . (18) S L_{A}=L_{B}. \tag*{(18)} S L A = L B . (18) We refer to the value of Eq. (17) as the period of the SLM, denoted by Z ~ \widetilde{Z} Z , and say that the SLM has multiplicity
μ = Z ~ lcm ( Z A , Z B ) . (19) \mu=\frac{\widetilde{Z}}{\operatorname{lcm}(Z_{A},Z_{B})}. \tag*{(19)} μ = lcm ( Z A , Z B ) Z . (19) Denote by SLM( A , B ) (\mathcal{A},\mathcal{B}) ( A , B ) the set of all SLMs from A \mathcal{A} A to B \mathcal{B} B , and those with multiplicity μ \mu μ by SLM( A , B ; μ ) (\mathcal{A},\mathcal{B};\mu) ( A , B ; μ ) .
Theorem 2. If J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) has a deformation gradient S S S , then ( L ~ A , L ~ B , S ) ∈ SLM ( A , B ) (\widetilde{L}_{A},\widetilde{L}_{B},S)\in\operatorname{SLM}(\mathcal{A},\mathcal{B}) ( L A , L B , S ) ∈ SLM ( A , B ) , where L ~ B \widetilde{L}_{B} L B is the shuffle lattice of J S − 1 \mathcal{J}S^{-1} J S − 1 and L ~ A = S − 1 L ~ B \widetilde{L}_{A}=S^{-1}\widetilde{L}_{B} L A = S − 1 L B .
Proof. Eq. (18) is already satisfied and we only need to show Eq. (17) . Consider a mapping p : A / L ~ A → B / L ~ B p:\mathcal{A}/\widetilde{L}_{A}\to\mathcal{B}/\widetilde{L}_{B} p : A / L A → B / L B such that the following diagram commutes:
A → J B + L ~ A ↓ ↓ + L ~ B A / L ~ A → p B / L ~ B (20) \begin{CD}
\mathcal{A} @>{\mathcal{J}}>> \mathcal{B} \\
@V{+\widetilde{L}_{A}}VV @VV{+\widetilde{L}_{B}}V \\
\mathcal{A}/\widetilde{L}_{A} @>{p}>> \mathcal{B}/\widetilde{L}_{B} \tag*{(20)}
\end{CD} A + L A ↓ ⏐ A / L A J p B ↓ ⏐ + L B B / L B (20)
i.e., p : a + L ~ A ↦ J ( a ) + L ~ B p:a+\widetilde{L}_{A}\mapsto\mathcal{J}(a)+\widetilde{L}_{B} p : a + L A ↦ J ( a ) + L B . To show that p p p is well-defined, we must prove its singlevaluedness. For any a 1 a_{1} a 1 and a 2 a_{2} a 2 in A \mathcal{A} A , we have
a 1 + L ~ A = a 2 + L ~ A (21) a_{1}+\widetilde{L}_{A}=a_{2}+\widetilde{L}_{A} \tag*{(21)} a 1 + L A = a 2 + L A (21)
⟺ ∃ t ∈ L ~ A , a 1 = a 2 + t (22) \Longleftrightarrow\ \exists t\in\widetilde{L}_{A},\quad a_{1}=a_{2}+t \tag*{(22)} ⟺ ∃ t ∈ L A , a 1 = a 2 + t (22)
⟺ ∃ t ∈ L ~ A , S a 1 = S a 2 + S t (23) \Longleftrightarrow\ \exists t\in\widetilde{L}_{A},\quad Sa_{1}=Sa_{2}+St \tag*{(23)} ⟺ ∃ t ∈ L A , S a 1 = S a 2 + S t (23)
⟺ ∃ t ′ ∈ L ~ B , S a 1 = S a 2 + t ′ (24) \Longleftrightarrow\ \exists t'\in\widetilde{L}_{B},\quad Sa_{1}=Sa_{2}+t' \tag*{(24)} ⟺ ∃ t ′ ∈ L B , S a 1 = S a 2 + t ′ (24)
⟺ ∃ t ′ ∈ L ~ B , J ( a 1 ) = J ( a 2 ) + t ′ (25) \Longleftrightarrow\ \exists t'\in\widetilde{L}_{B},\quad\mathcal{J}(a_{1})=\mathcal{J}(a_{2})+t' \tag*{(25)} ⟺ ∃ t ′ ∈ L B , J ( a 1 ) = J ( a 2 ) + t ′ (25)
⟺ J ( a 1 ) + L ~ B = J ( a 2 ) + L ~ B , (26) \Longleftrightarrow\quad\mathcal{J}(a_{1})+\widetilde{L}_{B}=\mathcal{J}(a_{2})+\widetilde{L}_{B}, \tag*{(26)} ⟺ J ( a 1 ) + L B = J ( a 2 ) + L B , (26)
where the shuffle property of J S − 1 : S A ⇝ B \mathcal{J}S^{-1}:S\mathcal{A}\rightsquigarrow\mathcal{B} J S − 1 : S A ⇝ B is used to derive Eq. (25) . The equivalence of Eqs. (21) and (26) means that p p p is injective, while p p p is surjective since J \mathcal{J} J is surjective. So far, we can see that p p p is bijective and thus Eq. (17) holds. ■
Definition 9 (Multiplicity). If J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) has a deformation gradient, we say that the ( L ~ A , L ~ B , S ) (\widetilde{L}_{A},\widetilde{L}_{B},S) ( L A , L B , S ) defined in Theorem 2 is the SLM of J \mathcal{J} J . In such case, we refer to the period and multiplicity of the SLM as those of J \mathcal{J} J . If the deformation gradient of J \mathcal{J} J does not exist, we say that the period and multiplicity of J \mathcal{J} J are ∞ \infty ∞ .
The multiplicity μ \mu μ defined in Eq. (19) is always a positive integer, since the period Z ~ \widetilde{Z} Z is a common multiple of Z A Z_{A} Z A and Z B Z_{B} Z B (Lemma 4). The value of μ \mu μ and Z ~ \widetilde{Z} Z reflect the intricacy of the CSM—the size of the smallest supercell required to describe it. It must be emphasized that μ \mu μ and Z ~ \widetilde{Z} Z are properties of the CSM, which are conceptually distinct from the number of atoms used in SSPT simulations. For example, MetaD calculations using up to ∼ 10 5 \sim10^{5} ∼ 1 0 5 atoms often yield CSMs with μ \mu μ and Z ~ \widetilde{Z} Z less than ∼ 10 1 \sim10^{1} ∼ 1 0 1 ; see Table II . Practically, we focus on solely those CSMs with finite multiplicity.
Table II. Some previously proposed CSMs (also known as mechanisms or paths). Congruent CSMs (e.g., the Bain mechanism and many shear mechanisms of the FCC-to-BCC transition [25 ] ) are only displayed once. See Ref. 26 for more details.
Congruence relations
Applying rigid transformations to A \mathcal{A} A and B \mathcal{B} B yields “congruent” yet so-called-theoretically different CSMs, as illustrated in Figure 5 . Such CSMs are equivalent as inputs to NEB-like methods, so we only need to enumerate all “noncongruent” CSMs. We denote by S A + t = { S a + t ∣ a ∈ A } \mathcal{S}\mathcal{A}+t=\{\mathcal{S}a+t\mid a\in\mathcal{A}\} S A + t = { S a + t ∣ a ∈ A } the crystal structure transformed from A \mathcal{A} A via an affine transformation ( S , t ) (S,t) ( S , t ) . In the same sense as in Eq. (10) , we have ( S , t ) ∈ CSM ( A , S A + t ) (S,t)\in\operatorname{CSM}(\mathcal{A},\mathcal{S}\mathcal{A}+t) ( S , t ) ∈ CSM ( A , S A + t ) .
Figure 5. An example of R A R_{A} R A (a rotation by 90 ∘ 90^\circ 9 0 ∘ ) and R B R_{B} R B (a rotation by 60 ∘ 60^\circ 6 0 ∘ ) being symmetry operations of A \mathcal{A} A (tetragonal) and B \mathcal{B} B (hexagonal), respectively. For each J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) , there exists a congruent R B J R A − 1 ∈ CSM ( A , B ) R_{B}\mathcal{J}R_{A}^{-1}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) R B J R A − 1 ∈ CSM ( A , B ) . Their respective SLMs are ( L ~ A , L ~ B , S ) (\widetilde{L}_{A},\widetilde{L}_{B},S) ( L A , L B , S ) and ( R A L ~ A , R B L ~ B , R B S R A − 1 ) (R_{A}\widetilde{L}_{A},R_{B}\widetilde{L}_{B},R_{B}SR_{A}^{-1}) ( R A L A , R B L B , R B S R A − 1 ) .
Definition 10 (Congruent CSM). We say that a CSM J ′ \mathcal{J}' J ′ is congruent to J ∈ CSM ( A , B ) \mathcal{J} \in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) if there exist proper rigid transformations ( R A , t A ) (R_A,t_A) ( R A , t A ) and ( R B , t B ) (R_B,t_B) ( R B , t B ) such that:
A → J B ( R A , t A ) ↓ ↓ ( R B , t B ) R A A + t A → J ′ R B B + t B (27) \begin{CD}
\mathcal{A} @>\mathcal{J}>> \mathcal{B}\\
@V{(R_A,t_A)}VV @VV{(R_B,t_B)}V\\
R_A\mathcal{A}+t_A @>>\mathcal{J}'> R_B\mathcal{B}+t_B \tag*{(27)}
\end{CD} A ( R A , t A ) ↓ ⏐ R A A + t A J J ′ B ↓ ⏐ ( R B , t B ) R B B + t B (27) i.e., J ′ = ( R B , t B ) J ( R A , t A ) − 1 \mathcal{J}'=(R_B,t_B)\mathcal{J}(R_A,t_A)^{-1} J ′ = ( R B , t B ) J ( R A , t A ) − 1 .
In general, two congruent CSMs have different domains and images, i.e., we have J ′ ∉ CSM ( A , B ) \mathcal{J}'\notin\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ′ ∈ / CSM ( A , B ) in Eq. (27) , unless ( R A , t A ) (R_A,t_A) ( R A , t A ) maps A \mathcal{A} A onto itself and ( R B , t B ) (R_B,t_B) ( R B , t B ) does the same. In this section, we specifically focus on the case where the proper rigid transformations are symmetry operations of the crystal structures, which define a congruence relation on CSM ( A , B ) \operatorname{CSM}(\mathcal{A},\mathcal{B}) CSM ( A , B ) . We denote by G A G_A G A the group formed by all proper rigid transformations ( R , t ) (R,t) ( R , t ) such that
A → ( R , t ) A , (28) \mathcal{A}\xrightarrow{(R,t)}\mathcal{A}, \tag*{(28)} A ( R , t ) A , (28)
and define the point group
G A ′ = { R ∣ ( R , t ) ∈ G A } . (29) G'_A=\{R\mid(R,t)\in G_A\}. \tag*{(29)} G A ′ = { R ∣ ( R , t ) ∈ G A } . (29)
It should be noted that G A ′ G'_A G A ′ is not a subgroup of G A G_A G A unless the lattice is symmorphic [42 ] , i.e., G A = G A ′ ⋉ L A G_A=G'_A\ltimes L_A G A = G A ′ ⋉ L A . We will see that G A ′ G'_A G A ′ and G B ′ G'_B G B ′ induce an equivalence relation on SLM ( A , B ) \operatorname{SLM}(\mathcal{A},\mathcal{B}) SLM ( A , B ) , which is inherited from Definition 10.
Lemma 1. If J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) is a shuffle, then for any t A , t B ∈ R 3 \mathbf{t}_A,\mathbf{t}_B\in\mathbb{R}^3 t A , t B ∈ R 3 , the composite mapping ( + t B ) ∘ J ∘ ( − t A ) (+\mathbf{t}_B)\circ\mathcal{J}\circ(-\mathbf{t}_A) ( + t B ) ∘ J ∘ ( − t A ) is also a shuffle from A + t A \mathcal{A}+\mathbf{t}_A A + t A to B + t B \mathcal{B}+\mathbf{t}_B B + t B , whose shuffle lattice is the same as J \mathcal{J} J .
Theorem 3. For any ( R A , t A ) ∈ G A (R_A,\mathbf{t}_A)\in G_A ( R A , t A ) ∈ G A , ( R B , t B ) ∈ G B (R_B,\mathbf{t}_B)\in G_B ( R B , t B ) ∈ G B , and J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) , the CSM J ′ \mathcal{J}' J ′ defined by Eq. (27) is also in CSM ( A , B ) \operatorname{CSM}(\mathcal{A},\mathcal{B}) CSM ( A , B ) . If J \mathcal{J} J has an SLM ( L ~ A , L ~ B , S ) (\widetilde{L}_A,\widetilde{L}_B,S) ( L A , L B , S ) , then J ′ \mathcal{J}' J ′ has the SLM ( R A L ~ A , R B L ~ B , R B S R A − 1 ) (R_A\widetilde{L}_A,R_B\widetilde{L}_B,R_BSR_A^{-1}) ( R A L A , R B L B , R B S R A − 1 ) .
Proof. When ( R A , t A ) ∈ G A (R_A,\mathbf{t}_A)\in G_A ( R A , t A ) ∈ G A and ( R B , t B ) ∈ G B (R_B,\mathbf{t}_B)\in G_B ( R B , t B ) ∈ G B , the bottom line of Eq. (27) becomes A → J ′ B \mathcal{A}\xrightarrow{\mathcal{J}'}\mathcal{B} A J ′ B . To show that J ′ \mathcal{J}' J ′ has the SLM ( R A L ~ A , R B L ~ B , R B S R A − 1 ) (R_A\widetilde{L}_A,R_B\widetilde{L}_B,R_BSR_A^{-1}) ( R A L A , R B L B , R B S R A − 1 ) , we only need to show that the deformed CSM
[ ( R B , t B ) J ( R A , t A ) − 1 ] ( R B S R A − 1 ) − 1 = ( R B , t B ) J R A − 1 ∘ ( − t A ) ∘ R A S − 1 R B − 1 = ( R B , t B ) J S − 1 R B − 1 ∘ ( − R B S R A − 1 t A ) (30) [(R_B,\mathbf{t}_B)\mathcal{J}(R_A,\mathbf{t}_A)^{-1}](R_BSR_A^{-1})^{-1}
=(R_B,\mathbf{t}_B)\mathcal{J}R_A^{-1}\circ(-\mathbf{t}_A)\circ R_AS^{-1}R_B^{-1}
=(R_B,\mathbf{t}_B)\mathcal{J}S^{-1}R_B^{-1}\circ(-R_BSR_A^{-1}\mathbf{t}_A) \tag*{(30)} [( R B , t B ) J ( R A , t A ) − 1 ] ( R B S R A − 1 ) − 1 = ( R B , t B ) J R A − 1 ∘ ( − t A ) ∘ R A S − 1 R B − 1 = ( R B , t B ) J S − 1 R B − 1 ∘ ( − R B S R A − 1 t A ) (30) is a shuffle with shuffle lattice R B L ~ B R_B\widetilde{L}_B R B L B . By Definition 6, a vector t ∈ R 3 \mathbf{t}\in\mathbb{R}^3 t ∈ R 3 is in L ~ B \widetilde{L}_B L B if and only if we have:
S A → J S − 1 B + t ↓ ↓ + t S A → J S − 1 B (31) \begin{CD}
S\mathcal{A} @>\mathcal{J}S^{-1}>> \mathcal{B}\\
@V{+\mathbf{t}}VV @VV{+\mathbf{t}}V\\
S\mathcal{A} @>>\mathcal{J}S^{-1}> \mathcal{B} \tag*{(31)}
\end{CD} S A + t ↓ ⏐ S A J S − 1 J S − 1 B ↓ ⏐ + t B (31) Applying ( R B , t B ) (R_B,\mathbf{t}_B) ( R B , t B ) to each crystal structure, we obtain:
R B S A + t B → ( R B , t B ) J S − 1 ( R B , t B ) − 1 R B B + t B ( R B , t B ) ↓ ↓ ( R B , t B ) R B S A + t B → ( R B , t B ) J S − 1 ( R B , t B ) − 1 R B B + t B (32) \begin{CD}
R_BS\mathcal{A}+\mathbf{t}_B @>{(R_B,\mathbf{t}_B)\mathcal{J}S^{-1}(R_B,\mathbf{t}_B)^{-1}}>> R_B\mathcal{B}+\mathbf{t}_B\\
@V{(R_B,\mathbf{t}_B)}VV @VV{(R_B,\mathbf{t}_B)}V\\
R_BS\mathcal{A}+\mathbf{t}_B @>>{(R_B,\mathbf{t}_B)\mathcal{J}S^{-1}(R_B,\mathbf{t}_B)^{-1}}> R_B\mathcal{B}+\mathbf{t}_B \tag*{(32)}
\end{CD} R B S A + t B ( R B , t B ) ↓ ⏐ R B S A + t B ( R B , t B ) J S − 1 ( R B , t B ) − 1 ( R B , t B ) J S − 1 ( R B , t B ) − 1 R B B + t B ↓ ⏐ ( R B , t B ) R B B + t B (32)
Taking the outer loop of the above diagram and using ( R B , t B ) ∈ G B (R_B,t_B)\in G_B ( R B , t B ) ∈ G B , we can see that t ∈ L ~ B t\in\widetilde{L}_B t ∈ L B if and only if:
R B S A + t B → ( R B , t B ) J S − 1 ( R B , t B ) − 1 B R B S A + t B → ( R B , t B ) J S − 1 ( R B , t B ) − 1 + R B t ↓ R B S ~ A + t B → ( R B , t B ) J S − 1 ( R B , t B ) − 1 B (33) \begin{aligned}
R_BSA+t_B &\xrightarrow{(R_B,t_B)\mathcal{J}S^{-1}(R_B,t_B)^{-1}} B \\
\mathrel{\phantom{R_BSA+t_B}} &\mathrel{\phantom{\xrightarrow{(R_B,t_B)\mathcal{J}S^{-1}(R_B,t_B)^{-1}}}} +R_Bt\downarrow\\
R_B\widetilde{S}A+t_B &\xrightarrow{(R_B,t_B)\mathcal{J}S^{-1}(R_B,t_B)^{-1}} B \tag*{(33)}
\end{aligned} R B S A + t B R B S A + t B R B S A + t B ( R B , t B ) J S − 1 ( R B , t B ) − 1 B ( R B , t B ) J S − 1 ( R B , t B ) − 1 + R B t ↓ ( R B , t B ) J S − 1 ( R B , t B ) − 1 B (33)
which implies that ( R B , t B ) J S − 1 ( R B , t B ) − 1 (R_B,t_B)\mathcal{J}S^{-1}(R_B,t_B)^{-1} ( R B , t B ) J S − 1 ( R B , t B ) − 1 is a shuffle with shuffle lattice R B L ~ B R_B\widetilde{L}_B R B L B . Eq. (32) differs from this shuffle by only a translation, and is therefore also a shuffle with shuffle lattice R B L ~ B R_B\widetilde{L}_B R B L B according to Lemma 1. ■
Definition 11 (Congruent SLM). We say that an SLM is congruent to ( L ~ A , L ~ B , S ) ∈ SLM ( A , B ) (\widetilde{L}_A,\widetilde{L}_B,S)\in\operatorname{SLM}(\mathcal{A},\mathcal{B}) ( L A , L B , S ) ∈ SLM ( A , B ) if it can be written as ( R A L ~ A , R B L ~ B , R B S R A − 1 ) (R_A\widetilde{L}_A,R_B\widetilde{L}_B,R_BSR_A^{-1}) ( R A L A , R B L B , R B S R A − 1 ) for some R A ∈ G A ′ , R B ∈ G B ′ R_A\in G'_A,R_B\in G'_B R A ∈ G A ′ , R B ∈ G B ′ .
Before describing how to exhaustively enumerate CSMs, we need to clarify what kind of CSM set is complete. We expect that they can, via NEB-like methods which allow rigid transformations, yield all SSPT mechanisms we are concerned with. Hence, there is no need to enumerate two or more congruent CSMs, and we say that a subset of X X X comprising CSMs or SLMs is complete as long as it contains an element of each congruence class in X X X .
Theorem 4. If X X X is a complete subset of SLM ( A , B ) \operatorname{SLM}(\mathcal{A},\mathcal{B}) SLM ( A , B ) , then ⋃ x ∈ X Y x \bigcup_{x\in X}Y_x ⋃ x ∈ X Y x is a complete subset of CSM ( A , B ) \operatorname{CSM}(\mathcal{A},\mathcal{B}) CSM ( A , B ) as long as Y x Y_x Y x is a complete subset of those CSMs with SLM x x x .
Proof. As long as J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) has an SLM, denoted by ( L ~ A , L ~ B , S ) (\widetilde{L}_A,\widetilde{L}_B,S) ( L A , L B , S ) , the completeness of X X X ensures that there exist R A ∈ G A ′ R_A\in G'_A R A ∈ G A ′ and R B ∈ G B ′ R_B\in G'_B R B ∈ G B ′ such that
( R A L ~ A , R B L ~ B , R B S R A − 1 ) ∈ X . (34) (R_A\widetilde{L}_A,R_B\widetilde{L}_B,R_BSR_A^{-1})\in X. \tag*{(34)} ( R A L A , R B L B , R B S R A − 1 ) ∈ X . (34)
Denote by x x x the left-hand side of Eq. (34) . Take t A , t B t_A,t_B t A , t B such that ( R A , t A ) ∈ G A (R_A,t_A)\in G_A ( R A , t A ) ∈ G A and ( R B , t B ) ∈ G B (R_B,t_B)\in G_B ( R B , t B ) ∈ G B . Since J \mathcal{J} J is congruent to ( R B , t B ) J ( R A , t A ) − 1 (R_B,t_B)\mathcal{J}(R_A,t_A)^{-1} ( R B , t B ) J ( R A , t A ) − 1 whose SLM is x x x (Theorem 3), the transitivity of congruence means that J \mathcal{J} J is also congruent to some CSM in Y x Y_x Y x . ■
Note that ⋃ x ∈ X Y x \bigcup_{x\in X}Y_x ⋃ x ∈ X Y x is also a complete subset of
⋃ R 1 ∈ SO ( 3 ) , τ 1 ∈ R 3 R 2 ∈ SO ( 3 ) , τ 2 ∈ R 3 CSM ( R 1 A + τ 1 , R 2 B + τ 2 ) , (35) \bigcup_{\substack{R_1\in\operatorname{SO}(3),\tau_1\in\mathbb{R}^3\\R_2\in\operatorname{SO}(3),\tau_2\in\mathbb{R}^3}}
\operatorname{CSM}(R_1\mathcal{A}+\tau_1,R_2\mathcal{B}+\tau_2), \tag*{(35)} R 1 ∈ SO ( 3 ) , τ 1 ∈ R 3 R 2 ∈ SO ( 3 ) , τ 2 ∈ R 3 ⋃ CSM ( R 1 A + τ 1 , R 2 B + τ 2 ) , (35)
which incorporates all possible initial and final structures of an SSPT. Hence, the CSMs in ⋃ x ∈ X Y x \bigcup_{x\in X}Y_x ⋃ x ∈ X Y x are sufficient as inputs to NEB-like methods. We will demonstrate how to compute X X X and Y x Y_x Y x in Section IV.
Representation and pruning
Before we describe the CRYSTMATCH method for exhaustively enumerating all noncongruent CSMs, it is necessary to represent CSMs as matrices for computer processing. We also need to introduce some physical constraints to make CSM ( A , B ) \operatorname{CSM}(\mathcal{A},\mathcal{B}) CSM ( A , B ) finite. In this section, we will show how to represent SLM and shuffle separately, and discuss the general form of pruning criteria. Afterwards, the finiteness of candidate CSMs will be proved. Symbols frequently used in this section are summarized in Table III .
Table III. Frequently used symbols in Section III A.
Representing crystal-structure matches
As elaborated in Section II, a CSM with finite multiplicity can always be decomposed into an SLM and a shuffle, both of which are cell-independent. However, just as an element of a vector space acquires a coordinate representation only after a basis is chosen, to represent CSMs as matrices, we also need to select a pair of “primitive cells” for A \mathcal{A} A and B \mathcal{B} B .
Representing sublattice matches
Definition 12 (Base Matrix). Let C ∈ R 3 × 3 C\in\mathbb{R}^{3\times3} C ∈ R 3 × 3 be a nonsingular matrix. We say that C ( Z 3 ) = { C k ∣ k ∈ Z 3 } C(\mathbb{Z}^3)=\{C\mathbf{k}\mid\mathbf{k}\in\mathbb{Z}^3\} C ( Z 3 ) = { C k ∣ k ∈ Z 3 } is the lattice generated by C C C , and C C C is the base matrix of C ( Z 3 ) C(\mathbb{Z}^3) C ( Z 3 ) .
Lemma 2. Any lattice has a base matrix.
Lemma 3. Let C , C ~ ∈ R 3 × 3 C,\widetilde{C}\in\mathbb{R}^{3\times3} C , C ∈ R 3 × 3 be nonsingular matrices. C ~ ( Z 3 ) \widetilde{C}(\mathbb{Z}^3) C ( Z 3 ) is a sublattice of C ( Z 3 ) C(\mathbb{Z}^3) C ( Z 3 ) if and only if there exists an M ∈ Z 3 × 3 M\in\mathbb{Z}^{3\times3} M ∈ Z 3 × 3 such that C ~ = C M \widetilde{C}=CM C = C M . In such case, the index of subgroup C ~ ( Z 3 ) \widetilde{C}(\mathbb{Z}^3) C ( Z 3 ) in C ( Z 3 ) C(\mathbb{Z}^3) C ( Z 3 ) is ∣ det M ∣ \lvert\det M\rvert ∣ det M ∣ .
Lemma 4. Let A \mathcal{A} A be a crystal structure and L ~ A \widetilde{L}_A L A its sublattice. Denote by k k k the index of subgroup L ~ A \widetilde{L}_A L A in L A L_A L A , which is finite by Lemmas 2 and 3. We have ∣ A / L ~ A ∣ = k Z A \lvert\mathcal{A}/\widetilde{L}_A\rvert=kZ_A ∣ A / L A ∣ = k Z A as long as Z A = ∣ A / L A ∣ Z_A=\lvert\mathcal{A}/L_A\rvert Z A = ∣ A / L A ∣ is finite.
Take C A , C B ∈ R 3 × 3 C_A,C_B\in\mathbb{R}^{3\times3} C A , C B ∈ R 3 × 3 that generate L A L_A L A and L B L_B L B , respectively. For each SLM ( L ~ A , L ~ B , S ) (\widetilde{L}_A,\widetilde{L}_B,S) ( L A , L B , S ) , there exists an M A ∈ Z 3 × 3 M_A\in\mathbb{Z}^{3\times3} M A ∈ Z 3 × 3 such that C A M A ( Z 3 ) = L ~ A C_AM_A(\mathbb{Z}^3)=\widetilde{L}_A C A M A ( Z 3 ) = L A . From Eq. (18) , we can see that S C A M A ( Z 3 ) = L ~ B SC_AM_A(\mathbb{Z}^3)=\widetilde{L}_B S C A M A ( Z 3 ) = L B , so S C A M A SC_AM_A S C A M A is a base matrix of L ~ B \widetilde{L}_B L B which equals C B M B C_BM_B C B M B for some M B ∈ Z 3 × 3 M_B\in\mathbb{Z}^{3\times3} M B ∈ Z 3 × 3 . This provides a way to represent an SLM ( L ~ A , L ~ B , S ) (\widetilde{L}_A,\widetilde{L}_B,S) ( L A , L B , S ) by a pair of integer matrices ( M A , M B ) (M_A,M_B) ( M A , M B ) satisfying
C A M A ( Z 3 ) = L ~ A , (36) C_AM_A(\mathbb{Z}^3)=\widetilde{L}_A, \tag*{(36)} C A M A ( Z 3 ) = L A , (36)
C B M B ( Z 3 ) = L ~ B , (37) C_BM_B(\mathbb{Z}^3)=\widetilde{L}_B, \tag*{(37)} C B M B ( Z 3 ) = L B , (37)
S C A M A = C B M B , (38) SC_AM_A=C_BM_B, \tag*{(38)} S C A M A = C B M B , (38)
Z A ∣ det M A ∣ = Z B ∣ det M B ∣ , (39) Z_A\lvert\det M_A\rvert=Z_B\lvert\det M_B\rvert, \tag*{(39)} Z A ∣ det M A ∣ = Z B ∣ det M B ∣ , (39)
where Eq. (39) is derived from Eq. (17) using Lemmas 3 and 4. We can also see that any nonsingular 3 × 3 3\times3 3 × 3 integer matrix pair ( M A , M B ) (M_A,M_B) ( M A , M B ) satisfying Eq. (39) determines an SLM according to Eqs. (36) –(38) . This representation of SLM is intuitive and extensively used [12 , 18 , 19 , 24 ] , but is not suitable for SLM enumeration since many different ( M A , M B ) (M_A,M_B) ( M A , M B ) can yield the same SLM [3 , 24 ] . To eliminate such representation redundancy, one may define a canonical base matrix for each lattice. The concepts of unimodular matrices and Hermite normal form will be useful, just as they play a crucial role in the Hart-Forcade theory [43 ] .
Definition 13 (Unimodular Matrix). Let Q ∈ Z n × n Q \in\mathbb{Z}^{n\times n} Q ∈ Z n × n be a nonsingular integer matrix. We say that Q Q Q is unimodular if any of the following equivalent propositions holds:
Q ( Z n ) = Z n , (40) Q(\mathbb{Z}^{n})=\mathbb{Z}^{n}, \tag*{(40)} Q ( Z n ) = Z n , (40) Q − 1 ∈ Z n × n , (41) Q^{-1}\in\mathbb{Z}^{n\times n}, \tag*{(41)} Q − 1 ∈ Z n × n , (41) det Q ∈ { + 1 , − 1 } . (42) \det Q\in\{+1,-1\}. \tag*{(42)} det Q ∈ { + 1 , − 1 } . (42)
We denote the matrix group formed by all unimodular matrices as GL ( n , Z ) \operatorname{GL}(n,\mathbb{Z}) GL ( n , Z ) .
Lemma 5. Two nonsingular matrices C , C ′ ∈ R 3 × 3 C,C' \in\mathbb{R}^{3\times3} C , C ′ ∈ R 3 × 3 generate the same lattice if and only if C − 1 C ′ ∈ GL ( 3 , Z ) C^{-1}C' \in\operatorname{GL}(3,\mathbb{Z}) C − 1 C ′ ∈ GL ( 3 , Z ) .
Definition 14 (HNF). Let H ∈ Z n × n H \in\mathbb{Z}^{n\times n} H ∈ Z n × n be a nonsingular matrix. We say that H H H is in Hermite normal form (HNF) if (1) H H H is lower triangular and (2) each off-diagonal element of H H H is nonnegative and strictly less than the diagonal element in its row. In other words, the elements of H H H satisfy
{ H i i > H i j ≥ 0 , if j < i , H i j = 0 , if j > i (43) \begin{cases}
H_{ii}>H_{ij}\ge0, & \text{if } j<i,\\
H_{ij}=0, & \text{if } j>i \tag*{(43)}
\end{cases} { H ii > H ij ≥ 0 , H ij = 0 , if j < i , if j > i (43)
Lemma 6. Let M ∈ Z n × n M \in\mathbb{Z}^{n\times n} M ∈ Z n × n be a nonsingular matrix. There exists a unique H ∈ Z n × n H \in\mathbb{Z}^{n\times n} H ∈ Z n × n in HNF and a unique Q ∈ GL ( n , Z ) Q \in\operatorname{GL}(n,\mathbb{Z}) Q ∈ GL ( n , Z ) such that
∃ Q ∈ GL ( n , Z ) , M = H Q . (44) \exists Q\in\operatorname{GL}(n,\mathbb{Z}),\quad M=HQ. \tag*{(44)} ∃ Q ∈ GL ( n , Z ) , M = H Q . (44) We say that H H H is the HNF of M M M .
Let hnf ( M ) \operatorname{hnf}(M) hnf ( M ) denote the HNF of M M M , and HNF ( k ) \operatorname{HNF}(k) HNF ( k ) denote all 3 × 3 3 \times3 3 × 3 HNFs with determinant k k k . Lemma 5 implies that ( M A , M B ) (M_A,M_B) ( M A , M B ) and ( M A ′ , M B ′ ) (M'_A,M'_B) ( M A ′ , M B ′ ) represent the same SLM if and only if ( M A ′ , M B ′ ) = ( M A Q ′ , M B Q ′ ) (M'_A,M'_B)=(M_AQ',M_BQ') ( M A ′ , M B ′ ) = ( M A Q ′ , M B Q ′ ) for some Q ′ ∈ GL ( 3 , Z ) Q'\in\operatorname{GL}(3,\mathbb{Z}) Q ′ ∈ GL ( 3 , Z ) .
To make the representation of SLM unique, one may use the mapping ( M A , M B ) ↦ ( H A , H B , Q ) (M_A,M_B)\mapsto(H_A,H_B,Q) ( M A , M B ) ↦ ( H A , H B , Q ) , where
H A = hnf ( M A ) , (45) H_A=\operatorname{hnf}(M_A), \tag*{(45)} H A = hnf ( M A ) , (45)
H B = hnf ( M B ) , (46) H_B=\operatorname{hnf}(M_B), \tag*{(46)} H B = hnf ( M B ) , (46)
Q = ( H B − 1 M B ) ( H A − 1 M A ) − 1 . (47) Q=(H_B^{-1}M_B)(H_A^{-1}M_A)^{-1}. \tag*{(47)} Q = ( H B − 1 M B ) ( H A − 1 M A ) − 1 . (47)
It maps the entire { ( M A Q ′ , M B Q ′ ) ∣ Q ′ ∈ GL ( 3 , Z ) } \{(M_AQ',M_BQ')\mid Q'\in\operatorname{GL}(3,\mathbb{Z})\} {( M A Q ′ , M B Q ′ ) ∣ Q ′ ∈ GL ( 3 , Z )} to a single integer-matrix triplet (IMT) [3 ] .
Definition 15 (IMT). Let A , B \mathcal{A},\mathcal{B} A , B be crystal structures and μ \mu μ a positive integer. We say that
IMT ( μ ) = HNF ( μ lcm ( Z A , Z B ) Z A ) × HNF ( μ lcm ( Z A , Z B ) Z B ) × GL ( 3 , Z ) (48) \operatorname{IMT}(\mu)=\operatorname{HNF}\left(\frac{\mu\operatorname{lcm}(Z_A,Z_B)}{Z_A}\right)
\times\operatorname{HNF}\left(\frac{\mu\operatorname{lcm}(Z_A,Z_B)}{Z_B}\right)\times\operatorname{GL}(3,\mathbb{Z}) \tag*{(48)} IMT ( μ ) = HNF ( Z A μ lcm ( Z A , Z B ) ) × HNF ( Z B μ lcm ( Z A , Z B ) ) × GL ( 3 , Z ) (48) is the set of all IMTs with multiplicity μ \mu μ .
Theorem 5. The mapping ( H A , H B , Q ) ↦ ( L ~ A , L ~ B , S ) (H_A,H_B,Q)\mapsto(\widetilde{L}_A,\widetilde{L}_B,S) ( H A , H B , Q ) ↦ ( L A , L B , S ) with
L ~ A = C A H A ( Z 3 ) , (49) \widetilde{L}_A=C_AH_A(\mathbb{Z}^{3}), \tag*{(49)} L A = C A H A ( Z 3 ) , (49) L ~ B = C B H B ( Z 3 ) , (50) \widetilde{L}_B=C_BH_B(\mathbb{Z}^{3}), \tag*{(50)} L B = C B H B ( Z 3 ) , (50) S = ( C B H B Q ) ( C A H A ) − 1 (51) S=(C_BH_BQ)(C_AH_A)^{-1} \tag*{(51)} S = ( C B H B Q ) ( C A H A ) − 1 (51) is a bijection from IMT ( μ ) \operatorname{IMT}(\mu) IMT ( μ ) to SLM ( A , B ; μ ) \operatorname{SLM}(\mathcal{A},\mathcal{B};\mu) SLM ( A , B ; μ ) .
Proof. ( L ~ A , L ~ B , S ) (\widetilde{L}_A,\widetilde{L}_B,S) ( L A , L B , S ) is an SLM since S L ~ A = L ~ B S\widetilde{L}_A=\widetilde{L}_B S L A = L B and
∣ A / L ~ A ∣ = Z A det H A (52) |\mathcal{A}/\widetilde{L}_A|=Z_A\det H_A \tag*{(52)} ∣ A / L A ∣ = Z A det H A (52)
= μ lcm ( Z A , Z B ) (53) =\mu\operatorname{lcm}(Z_A,Z_B) \tag*{(53)} = μ lcm ( Z A , Z B ) (53)
= Z B det H B (54) =Z_B\det H_B \tag*{(54)} = Z B det H B (54)
= ∣ B / L ~ B ∣ . (55) =|\mathcal{B}/\widetilde{L}_B|. \tag*{(55)} = ∣ B / L B ∣. (55)
where Lemmas 3 and 4 are used to derive Eqs. (52) and (55) . Definition 15 ensures Eqs. (53) and (54) , so that the multiplicity of ( L ~ A , L ~ B , S ) (\widetilde{L}_A,\widetilde{L}_B,S) ( L A , L B , S ) is μ \mu μ . Conversely, for each ( L ~ A , L ~ B , S ) ∈ SLM ( A , B ; μ ) (\widetilde{L}_A,\widetilde{L}_B,S)\in\operatorname{SLM}(\mathcal{A},\mathcal{B};\mu) ( L A , L B , S ) ∈ SLM ( A , B ; μ ) , L ~ A \widetilde{L}_A L A has a unique base matrix C A H A C_AH_A C A H A , where H A H_A H A is in HNF (Lemmas 5 and 6) with determinant Z ~ / Z A = μ \widetilde{Z}/Z_A=\mu Z / Z A = μ (Lemmas 3 and 4), and so does L ~ B \widetilde{L}_B L B . Since H A H_A H A and H B H_B H B are determined, S S S further determines Q Q Q by Eq. (51) . Therefore, every SLM is associated with a unique IMT.
Theorem 5 allows us to focus on the enumeration of IMT ( μ ) \operatorname{IMT}(\mu) IMT ( μ ) from now on, which is far more intuitive than the enumeration of SLMs.
Representing shuffles
Definition 16 (Motif). Let A \mathcal{A} A be a crystal structure and L ~ A \widetilde{L}_{A} L A a sublattice of A \mathcal{A} A . We say that { a 1 , a 2 , … , a n } ⊂ A \{a_{1},a_{2},\ldots,a_{n}\}\subset\mathcal{A} { a 1 , a 2 , … , a n } ⊂ A is an L ~ A \widetilde{L}_{A} L A -motif of A \mathcal{A} A if a 1 , … , a n a_{1},\ldots,a_{n} a 1 , … , a n are L ~ A \widetilde{L}_{A} L A -inequivalent and n = ∣ A / L ~ A ∣ n=\lvert\mathcal{A}/\widetilde{L}_{A}\rvert n = ∣ A / L A ∣ .
Theorem 6. Let ( L ~ A , L ~ B , S ) (\widetilde{L}_{A},\widetilde{L}_{B},S) ( L A , L B , S ) be an SLM with period Z ~ \widetilde{Z} Z , { a 1 , … , a Z ~ } \{a_{1},\ldots,a_{\widetilde{Z}}\} { a 1 , … , a Z } an L ~ A \widetilde{L}_{A} L A -motif of A \mathcal{A} A , and { b 1 , … , b Z ~ } \{b_{1},\ldots,b_{\widetilde{Z}}\} { b 1 , … , b Z } an L ~ B \widetilde{L}_{B} L B -motif of B \mathcal{B} B . If J ∈ CSM ( A , B ) J\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) has the SLM ( L ~ A , L ~ B , S ) (\widetilde{L}_{A},\widetilde{L}_{B},S) ( L A , L B , S ) , there exist a unique permutation p ∈ Sym ( Z ~ ) p\in\operatorname{Sym}(\widetilde{Z}) p ∈ Sym ( Z ) and unique t 1 , … , t Z ~ ∈ L ~ B t_{1},\ldots,t_{\widetilde{Z}}\in\widetilde{L}_{B} t 1 , … , t Z ∈ L B such that
∀ i ∈ { 1 , … , Z ~ } , J ( a i ) = b p ( i ) + t i . (56) \forall i\in\{1,\ldots,\widetilde{Z}\},\quad J(a_{i})=b_{p(i)}+t_{i}. \tag*{(56)} ∀ i ∈ { 1 , … , Z } , J ( a i ) = b p ( i ) + t i . (56) Furthermore, if both J 1 J_{1} J 1 and J 2 J_{2} J 2 have ( L ~ A , L ~ B , S ) (\widetilde{L}_{A},\widetilde{L}_{B},S) ( L A , L B , S ) , then J 1 = J 2 J_{1}=J_{2} J 1 = J 2 if and only if they have the same ( p , t 1 , … , t Z ~ ) (p,t_{1},\ldots,t_{\widetilde{Z}}) ( p , t 1 , … , t Z ) .
Proof. In the proof of Theorem 2, we have already shown that a + L ~ A ↦ J ( a ) + L ~ B a+\widetilde{L}_{A}\mapsto J(a)+\widetilde{L}_{B} a + L A ↦ J ( a ) + L B is a bijection from A / L ~ A \mathcal{A}/\widetilde{L}_{A} A / L A to B / L ~ B \mathcal{B}/\widetilde{L}_{B} B / L B . Therefore, the images of different a 1 , … , a Z ~ a_{1},\ldots,a_{\widetilde{Z}} a 1 , … , a Z under J J J are in different b 1 + L ~ B , … , b Z ~ + L ~ B b_{1}+\widetilde{L}_{B},\ldots,b_{\widetilde{Z}}+\widetilde{L}_{B} b 1 + L B , … , b Z + L B . This determines p p p which is a permutation on { 1 , … , Z ~ } \{1,\ldots,\widetilde{Z}\} { 1 , … , Z } , and t 1 , … , t Z ~ t_{1},\ldots,t_{\widetilde{Z}} t 1 , … , t Z is also uniquely determined by Eq. (56) . Furthermore, since each element in A \mathcal{A} A can be uniquely decomposed as a = a i + t a=a_{i}+t a = a i + t for some i ∈ { 1 , … , Z ~ } i\in\{1,\ldots,\widetilde{Z}\} i ∈ { 1 , … , Z } and t ∈ L ~ A t\in\widetilde{L}_{A} t ∈ L A , we have
∀ a i + t ∈ A , J ( a i + t ) = b p ( i ) + t i + S t . (57) \forall a_{i}+t\in\mathcal{A},\quad J(a_{i}+t)=b_{p(i)}+t_{i}+St. \tag*{(57)} ∀ a i + t ∈ A , J ( a i + t ) = b p ( i ) + t i + S t . (57) which is derived from Eq. (56) and the following commutative diagram:
A → S S A → J B + t ↓ + S t ↓ + S t ↓ A → S S A → J B (58) \begin{CD}
\mathcal{A} @>S>> S\mathcal{A} @>J>> \mathcal{B} \\
@V{+t}VV @V{+St}VV @V{+St}VV \\
\mathcal{A} @>S>> S\mathcal{A} @>{J}>> \mathcal{B} \tag*{(58)}
\end{CD} A + t ↓ ⏐ A S S S A + S t ↓ ⏐ S A J J B + S t ↓ ⏐ B (58) From Eq. (57) we can see that ( p , t 1 , … , t Z ~ ) (p,t_{1},\ldots,t_{\widetilde{Z}}) ( p , t 1 , … , t Z ) completely determines a CSM with the SLM ( L ~ A , L ~ B , S ) (\widetilde{L}_{A},\widetilde{L}_{B},S) ( L A , L B , S ) .
Given the SLM, Theorem 6 uniquely represents each CSM as a permutation p p p and Z ~ \widetilde{Z} Z elements of L ~ B \widetilde{L}_{B} L B . The underlying reason is that each ( p , t 1 , … , t Z ~ ) (p,t_{1},\ldots,t_{\widetilde{Z}}) ( p , t 1 , … , t Z ) actually represents a shuffle, which we refer to as the “permutation with class-wise translations” (PCT) representation, as illustrated in Figure 6 . We denote by J p , t 1 , … , t Z ~ J_{p,t_{1},\ldots,t_{\widetilde{Z}}} J p , t 1 , … , t Z the CSM determined by Eq. (57) .
Figure 6. Two PCTs representing J 1 , J 2 : S A ⇝ B J_{1},J_{2}:S\mathcal{A}\rightsquigarrow\mathcal{B} J 1 , J 2 : S A ⇝ B with the same shuffle lattice (gray grids), respectively. Both { S a i } \{Sa_{i}\} { S a i } , the motif of S A S\mathcal{A} S A (cyan) and { b i } \{b_{i}\} { b i } , the motif of B \mathcal{B} B (blue) are labeled by 1–4. Every pink atom J ( a i ) J(a_{i}) J ( a i ) is both the image of S a i Sa_{i} S a i under J S − 1 J S^{-1} J S − 1 and an element of B \mathcal{B} B , which can be written as b p ( i ) + t i b_{p(i)}+t_{i} b p ( i ) + t i . Therefore, the PCT representation of a shuffle can be viewed as the unique map b i ↦ b p ( i ) + t i b_{i}\mapsto b_{p(i)}+t_{i} b i ↦ b p ( i ) + t i that makes the triangle in the figure commute, where the horizontal gray arrow represents S a i ↦ b i Sa_{i}\mapsto b_{i} S a i ↦ b i (the canonical bijection between motifs). The pink text shows the specific PCTs representing J 1 J_{1} J 1 and J 2 J_{2} J 2 , where p = ( 1 2 3 4 1 3 2 4 ) p=\begin{pmatrix}1&2&3&4\\1&3&2&4\end{pmatrix} p = ( 1 1 2 3 3 2 4 4 ) .
Definition 17 (PCT). Given a mapping
( L ~ A , L ~ B , S ) ↦ ( a 1 , … , a Z ~ , b 1 , … , b Z ~ ) , (59) (\widetilde{L}_{A},\widetilde{L}_{B},S)\mapsto(a_{1},\ldots,a_{\widetilde{Z}},b_{1},\ldots,b_{\widetilde{Z}}), \tag*{(59)} ( L A , L B , S ) ↦ ( a 1 , … , a Z , b 1 , … , b Z ) , (59) that determines an L ~ A \widetilde{L}_{A} L A -motif of A \mathcal{A} A and an L ~ B \widetilde{L}_{B} L B -motif of B \mathcal{B} B for each SLM in SLM ( A , B ) \operatorname{SLM}(\mathcal{A},\mathcal{B}) SLM ( A , B ) . We say that
PCT ( L ~ A , L ~ B , S ) = { ( p , t 1 , … , t Z ~ ) ∈ Sym ( Z ~ ) × L ~ B Z ~ ∣ ∀ i , χ A ( a i ) = χ B ( b p ( i ) ) } . (60) \operatorname{PCT}(\widetilde{L}_{A},\widetilde{L}_{B},S)=\left\{(p,t_{1},\ldots,t_{\widetilde{Z}})\in\operatorname{Sym}(\widetilde{Z})\times\widetilde{L}_{B}^{\widetilde{Z}}\mid\forall i,\ \chi_{A}(a_{i})=\chi_{B}(b_{p(i)})\right\}. \tag*{(60)} PCT ( L A , L B , S ) = { ( p , t 1 , … , t Z ) ∈ Sym ( Z ) × L B Z ∣ ∀ i , χ A ( a i ) = χ B ( b p ( i ) ) } . (60)
is the set of all PCTs with SLM ( L ~ A , L ~ B , S ) (\widetilde{L}_{A},\widetilde{L}_{B},S) ( L A , L B , S ) , which depends only on the SLM and the mapping.
Note that p p p can be stored as a permutation matrix, and L ~ B \widetilde{L}_{B} L B is isomorphic to Z 3 \mathbb{Z}^{3} Z 3 . In this sense, all the ingredients of a CSM can be represented as integer matrices. Given C ^ A , C ^ B \widehat{C}_{A},\widehat{C}_{B} C A , C B , and a deterministic way to choose the L ~ A \widetilde{L}_{A} L A - and L ~ B \widetilde{L}_{B} L B -motifs for each SLM, one can reproduce any CSM from its associated IMT and PCT.
Pruning criteria
As a one-to-one correspondence between infinite sets, the CSM has infinitely many possibilities. Fortunately, we are only concerned with the CSMs of those MEPs with low energy barriers. Hence, many CSMs can be excluded, leaving only a finite number of candidates.
Strain energy density
From an energetic perspective, the constraint on strain is necessary, since excessive deformation would lead to a large strain energy. We are only concerned with those CSMs whose deformation gradients satisfy
w ( S ) ≤ w max , (61) w(S)\leq w_{\max}, \tag*{(61)} w ( S ) ≤ w m a x , (61)
where w ( S ) w(S) w ( S ) denotes the strain energy density associated with the deformation gradient S S S , and w max w_{\max} w m a x is a truncation threshold. When searching for the CSM of the lowest-barrier MEP, one may let w max w_{\max} w m a x be the minimum Δ ‡ \Delta^{\ddagger} Δ ‡ -density among known SSPTs.
Lemma 7 (SVD). If S ∈ R 3 × 3 S \in\mathbb{R}^{3 \times3} S ∈ R 3 × 3 has a positive determinant, there exist U , V ∈ S O ( 3 ) U,V \in\mathrm{SO}(3) U , V ∈ SO ( 3 ) and unique s 1 ≥ s 2 ≥ s 3 > 0 s_1 \ge s_2 \ge s_3 > 0 s 1 ≥ s 2 ≥ s 3 > 0 such that S = U Σ V T S=U\Sigma V^{\mathsf{T}} S = U Σ V T , where Σ = diag ( s 1 , s 2 , s 3 ) \Sigma=\operatorname{diag}(s_1,s_2,s_3) Σ = diag ( s 1 , s 2 , s 3 ) .
Lemma 7 is known as the singular value decomposition (SVD) and s i s_i s i is referred to as the i i i -th singular value of S S S [44 ] , usually denoted by σ i ( S ) \sigma_i(S) σ i ( S ) . A direct corollary is the polar decomposition (PD), which states that a deformation gradient can always be uniquely factorized into a positive-definite transformation and a rotation, as
S = ( U V T ) ( V Σ V T ) = ( S S T S − 1 ) S T S . (62) S=(UV^{\mathsf{T}})(V\Sigma V^{\mathsf{T}})=\left(S\sqrt{S^{\mathsf{T}}S}^{-1}\right)\sqrt{S^{\mathsf{T}}S}. \tag*{(62)} S = ( U V T ) ( V Σ V T ) = ( S S T S − 1 ) S T S . (62)
Note that the rotation U V T UV^{\mathsf{T}} U V T does not contribute to the strain energy, and the positive-definite V Σ V T V\Sigma V^{\mathsf{T}} V Σ V T simply scales the space by s i s_i s i along v i \mathbf{v}_i v i for i = 1 , 2 , 3 i=1,2,3 i = 1 , 2 , 3 , where v i \mathbf{v}_i v i denotes the i i i -th column of V V V . We estimate the strain energy according to the diagram:
A → J B ↓ V Σ V T ↓ U Σ U T V Σ 1 2 V T A → J ~ V Σ − 1 2 U T B → U V T U Σ − 1 2 U T B (63) \begin{aligned}
\mathcal{A} &\xrightarrow{\mathcal{J}} \mathcal{B}\\
\Big\downarrow\sqrt{V\Sigma V^{\mathsf{T}}} && \Big\downarrow\sqrt{U\Sigma U^{\mathsf{T}}}\\
V\Sigma^{\frac{1}{2}}V^{\mathsf{T}}\mathcal{A} &\xrightarrow{\widetilde{\mathcal{J}}} V\Sigma^{-\frac{1}{2}}U^{\mathsf{T}}\mathcal{B} \xrightarrow{UV^{\mathsf{T}}} U\Sigma^{-\frac{1}{2}}U^{\mathsf{T}}\mathcal{B} \tag*{(63)}
\end{aligned} A ↓ ⏐ V Σ V T V Σ 2 1 V T A J B J V Σ − 2 1 U T B U V T U Σ − 2 1 U T B ↓ ⏐ U Σ U T (63)
where J ~ \widetilde{\mathcal{J}} J is defined as the unique shuffle that makes the diagram commute, which we refer to as the standard shuffle of J \mathcal{J} J . Note that the two vertical arrows are pure deformations, while all horizontal arrows in the second row involve no strain. Based on this, w w w is estimated as the sum of the strain energies associated with the deformation of A \mathcal{A} A by V Σ V T \sqrt{V\Sigma V^{\mathsf{T}}} V Σ V T and the deformation of B \mathcal{B} B by U Σ U T − 1 \sqrt{U\Sigma U^{\mathsf{T}}}^{-1} U Σ U T − 1 , namely,
w ( S ) = 1 2 ∑ i , j , k , l = 1 3 { Y i j k l A [ V ( Σ 1 2 − I ) V T ] i j [ V ( Σ 1 2 − I ) V T ] k l + Y i j k l B [ U ( Σ − 1 2 − I ) U T ] i j [ U ( Σ − 1 2 − I ) U T ] k l } (64) w(S)=\frac{1}{2}\sum_{i,j,k,l=1}^{3}\left\{Y^{A}_{ijkl}\left[V\left(\Sigma^{\frac{1}{2}}-I\right)V^{\mathsf{T}}\right]_{ij}\left[V\left(\Sigma^{\frac{1}{2}}-I\right)V^{\mathsf{T}}\right]_{kl}+Y^{B}_{ijkl}\left[U\left(\Sigma^{-\frac{1}{2}}-I\right)U^{\mathsf{T}}\right]_{ij}\left[U\left(\Sigma^{-\frac{1}{2}}-I\right)U^{\mathsf{T}}\right]_{kl}\right\} \tag*{(64)} w ( S ) = 2 1 i , j , k , l = 1 ∑ 3 { Y ij k l A [ V ( Σ 2 1 − I ) V T ] ij [ V ( Σ 2 1 − I ) V T ] k l + Y ij k l B [ U ( Σ − 2 1 − I ) U T ] ij [ U ( Σ − 2 1 − I ) U T ] k l } (64)
= 1 2 ∑ a , b = 1 3 ∑ i , j , k , l = 1 3 [ ( s a − 1 ) ( s b − 1 ) Y i j k l A V i a V j a V k b V l b + ( 1 s a − 1 ) ( 1 s b − 1 ) Y i j k l B U i a U j a U k b U l b ] . (65) =\frac{1}{2}\sum_{a,b=1}^{3}\sum_{i,j,k,l=1}^{3}\left[\left(\sqrt{s_a}-1\right)\left(\sqrt{s_b}-1\right)Y^{A}_{ijkl}V_{ia}V_{ja}V_{kb}V_{lb}+\left(\frac{1}{\sqrt{s_a}}-1\right)\left(\frac{1}{\sqrt{s_b}}-1\right)Y^{B}_{ijkl}U_{ia}U_{ja}U_{kb}U_{lb}\right]. \tag*{(65)} = 2 1 a , b = 1 ∑ 3 i , j , k , l = 1 ∑ 3 [ ( s a − 1 ) ( s b − 1 ) Y ij k l A V ia V j a V k b V l b + ( s a 1 − 1 ) ( s b 1 − 1 ) Y ij k l B U ia U j a U k b U l b ] . (65)
where Y i j k l A Y^{A}_{ijkl} Y ij k l A and Y i j k l B Y^{B}_{ijkl} Y ij k l B denote the elastic (stiffness) tensors of A \mathcal{A} A and B \mathcal{B} B , respectively. Substituting (65) into (61) yields the inequality that S S S must satisfy, which varies depending on the material’s mechanical properties. It is worth noting that w w w is a congruence-class function , i.e.,
∀ R A ∈ G A ′ , ∀ R B ∈ G B ′ , w ( R B S R A − 1 ) = w ( S ) . (66) \forall R_A \in G'_A,\ \forall R_B \in G'_B,\quad w(R_BSR_A^{-1})=w(S). \tag*{(66)} ∀ R A ∈ G A ′ , ∀ R B ∈ G B ′ , w ( R B S R A − 1 ) = w ( S ) . (66)
This can be seen from Lemma 7, where R A R_A R A and R B R_B R B only contributes to V V V and U U U , respectively. As symmetry operations of A \mathcal{A} A and B \mathcal{B} B , the elastic tensors Y i j k l A Y^{A}_{ijkl} Y ij k l A and Y i j k l B Y^{B}_{ijkl} Y ij k l B are invariant under R A R_A R A and R B R_B R B , respectively. Hence, SLMs are pruned by congruence classes under (61) .
Shuffle distance
For each SLM, there are still infinitely many possible CSMs—even a single atom a ∈ A a \in\mathcal{A} a ∈ A has infinitely many choices of its counterpart J ( a ) \mathcal{J}(a) J ( a ) . An intuitive constraint is that J ( a ) \mathcal{J}(a) J ( a ) should not be too far from a a a . This is not an energetic consideration, but rather an empirical one, as discussed in Ref. 25, where the average distance traveled by the atoms is shown to be a key indicator. However, the average distance between J ( a ) \mathcal{J}(a) J ( a ) and a a a goes to infinity unless S = I S=I S = I , i.e., J \mathcal{J} J is a shuffle. Therefore, the appropriate way to define the “average distance” is to consider a shuffle associated with J \mathcal{J} J . Here, we use the standard shuffle J \mathcal{J} J defined in (63) instead of J S − 1 \mathcal{J}S^{-1} J S − 1 to ensure the metric symmetry between the initial and final structures. As shorthand, denote by L ~ \widetilde{\mathcal{L}} L the shuffle lattice of J ~ \widetilde{\mathcal{J}} J and let A ~ = V Σ 1 2 V T A \widetilde{\mathcal{A}}=V\Sigma^{\frac{1}{2}}V^{\mathsf{T}}\mathcal{A} A = V Σ 2 1 V T A and B ~ = V Σ − 1 2 U T B \widetilde{\mathcal{B}}=V\Sigma^{-\frac{1}{2}}U^{\mathsf{T}}\mathcal{B} B = V Σ − 2 1 U T B , which are all uniquely determined by the SLM.
Definition 18 (Shuffle Distance). Let J ∈ CSM ( A , B ) \mathcal{J}\in\operatorname{CSM}(\mathcal{A},\mathcal{B}) J ∈ CSM ( A , B ) be a CSM with period Z ~ \widetilde{Z} Z . We say that the shuffle distance of J \mathcal{J} J is
d ^ ( J ) = ( ∑ i = 1 Z ~ θ i ∣ J ~ ( a ~ i ) − a ~ i ∣ ℓ ) 1 / ℓ , (67) \hat{d}(\mathcal{J})=\left(\sum_{i=1}^{\widetilde{Z}}\theta_i\left\lvert\widetilde{\mathcal{J}}(\widetilde{\mathbf{a}}_i)-\widetilde{\mathbf{a}}_i\right\rvert^\ell\right)^{1/\ell}, \tag*{(67)} d ^ ( J ) = i = 1 ∑ Z θ i J ( a i ) − a i ℓ 1/ ℓ , (67)
where ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 specifies the norm, { a ~ 1 , … , a ~ Z ~ } \{\widetilde{\mathbf{a}}_1,\ldots,\widetilde{\mathbf{a}}_{\widetilde{Z}}\} { a 1 , … , a Z } is an L ~ \widetilde{\mathcal{L}} L -motif of A ~ \widetilde{\mathcal{A}} A , and θ i > 0 \theta_i>0 θ i > 0 is a normalized weight that only depends on the atomic species of a ~ i \widetilde{\mathbf{a}}_i a i (e.g., a constant, or atomic mass). One may adopt ℓ = 2 \ell=2 ℓ = 2 for the root-mean-square distance (RMSD), or ℓ = 1 \ell=1 ℓ = 1 for the arithmetic mean distance.
Eq. 9 ensures the value of (67) to be independent of the choice of the motif so that d ^ \hat{d} d ^ is well-defined. However, congruent CSMs may not necessarily have the same d ^ \hat{d} d ^ , which is undesirable since they are equivalent as inputs to NEB-like methods. To address this issue, we define
d ( J ) = min τ ∈ R 3 ( ∑ i = 1 Z ~ θ i ∣ J ~ ( a ~ i ) + τ − a ~ i ∣ ℓ ) 1 / ℓ , (68) d(\mathcal{J})=\min_{\boldsymbol{\tau}\in\mathbb{R}^3}\left(\sum_{i=1}^{\widetilde{Z}}\theta_i\left\lvert\widetilde{\mathcal{J}}(\widetilde{\mathbf{a}}_i)+\boldsymbol{\tau}-\widetilde{\mathbf{a}}_i\right\rvert^\ell\right)^{1/\ell}, \tag*{(68)} d ( J ) = τ ∈ R 3 min i = 1 ∑ Z θ i J ( a i ) + τ − a i ℓ 1/ ℓ , (68)
which equals the minimum d ^ \hat{d} d ^ among all CSMs of the form ( + τ B ) ∘ J ∘ ( − τ A ) ∈ CSM ( A + τ A , B + τ B ) (+\tau_{B}) \circ\mathcal{J} \circ(-\tau_{A}) \in\operatorname{CSM}(A+\tau_{A}, B+\tau_{B}) ( + τ B ) ∘ J ∘ ( − τ A ) ∈ CSM ( A + τ A , B + τ B ) . Similar to the proof of Theorem 3, one can show that any J ′ \mathcal{J}' J ′ congruent to J \mathcal{J} J has a standard shuffle that differs from ( R , t ) J ~ ( R , t ) − 1 (R,t)\widetilde{\mathcal{J}}(R,t)^{-1} ( R , t ) J ( R , t ) − 1 by just a translation, implying that
d ( J ′ ) = d [ ( R , t ) J ~ ( R , t ) − 1 ] = d ( J ~ ) = d ( J ) , (69) d(\mathcal{J}')=d[(R,t)\widetilde{\mathcal{J}}(R,t)^{-1}]=d(\widetilde{\mathcal{J}})=d(\mathcal{J}), \tag*{(69)} d ( J ′ ) = d [( R , t ) J ( R , t ) − 1 ] = d ( J ) = d ( J ) , (69)
where we have used the fact that ( R , t ) (R,t) ( R , t ) is an isometry. Eq. (69) means that congruent CSMs have the same d d d , so that as long as d ( J ) d(\mathcal{J}) d ( J ) exceeds the threshold d max d_{\max} d m a x , we can exclude all CSMs congruent to J \mathcal{J} J .
Finiteness of candidate crystal-structure matches
As shown in Figure 2 , the enumeration includes a CSM J \mathcal{J} J with multiplicity μ \mu μ and deformation gradient S S S if
μ ≤ μ max , (70) \mu\le\mu_{\max}, \tag*{(70)} μ ≤ μ m a x , (70)
w ( S ) ≤ w max , (71) w(S) \le w_{\max}, \tag*{(71)} w ( S ) ≤ w m a x , (71)
d ( J ) ≤ d max . (72) d(\mathcal{J}) \le d_{\max}. \tag*{(72)} d ( J ) ≤ d m a x . (72)
They have all been detailed earlier, except for Eq. (70) , which can be regarded as an empirical constraint inferred from Table II —despite MD and MetaD simulations using far more than 10 3 10^3 1 0 3 atoms, the intricacy of the CSMs they produce remain Z ~ ∼ 10 1 \widetilde{Z} \sim10^1 Z ∼ 1 0 1 . We emphasize that w max w_{\max} w m a x can depend on μ \mu μ , and d max d_{\max} d m a x can depend on the SLM of J \mathcal{J} J . For example, one might want to slacken the constraints on w max w_{\max} w m a x and d max d_{\max} d m a x when μ \mu μ is small. One may also set d max d_{\max} d m a x for each SLM to 110% of the lowest d d d value among all CSMs with that SLM. In a word, different subtrees in Figure 2 can be pruned with different thresholds. We denote by CSM ⋆ ( A , B ) \operatorname{CSM}^{\star}(A,B) CSM ⋆ ( A , B ) the set of all CSMs in CSM ( A , B ) \operatorname{CSM}(A,B) CSM ( A , B ) that satisfy Eqs. (70) –(72) , and their SLMs by SLM ⋆ ( A , B ) \operatorname{SLM}^{\star}(A,B) SLM ⋆ ( A , B ) .
Theorem 7. SLM ⋆ ( A , B ; μ ) \operatorname{SLM}^{\star}(A,B;\mu) SLM ⋆ ( A , B ; μ ) is finite regardless of the values of μ \mu μ and w max w_{\max} w m a x .
Proof. There exists a σ max \sigma_{\max} σ m a x such that σ 1 ( S ) < σ max \sigma_{1}(S)<\sigma_{\max} σ 1 ( S ) < σ m a x implies Eq. (71) ; otherwise, infinite strain would leads to infinite strain energy. We only need to prove that only a finite number of ( H A , H B , Q ) ∈ IMT ( μ ) (H_{A},H_{B},Q)\in\operatorname{IMT}(\mu) ( H A , H B , Q ) ∈ IMT ( μ ) satisfy σ 1 ( S ) < σ max \sigma_{1}(S)<\sigma_{\max} σ 1 ( S ) < σ m a x . Since HNF ( k ) \operatorname{HNF}(k) HNF ( k ) is finite, the number of possible values of ( H A , H B ) (H_{A},H_{B}) ( H A , H B ) is already finite. It is sufficient to show that given ( H A , H B ) (H_{A},H_{B}) ( H A , H B ) , the number of possible values of Q Q Q is finite. This is due to the fact that the absolute value of any matrix element of Q Q Q does not exceed
σ 1 ( Q ) = σ 1 ( H B − 1 C B − 1 S C A H A ) (73) \sigma_{1}(Q)=\sigma_{1}(H_{B}^{-1}C_{B}^{-1}S C_{A}H_{A}) \tag*{(73)} σ 1 ( Q ) = σ 1 ( H B − 1 C B − 1 S C A H A ) (73)
≤ σ 1 ( H B − 1 ) σ 1 ( C B − 1 ) σ 1 ( C A ) σ 1 ( H A ) σ max , (74) \le\sigma_{1}(H_{B}^{-1})\sigma_{1}(C_{B}^{-1})\sigma_{1}(C_{A})\sigma_{1}(H_{A})\sigma_{\max}, \tag*{(74)} ≤ σ 1 ( H B − 1 ) σ 1 ( C B − 1 ) σ 1 ( C A ) σ 1 ( H A ) σ m a x , (74)
where Eq. (73) is derived from Eq. (51) .
Theorem 8. For any given SLM and d max d_{\max} d m a x , the number of noncongruent CSMs that have this SLM and satisfy Eq. (72) is finite.
Proof. We assume by contradiction that there are infinitely many noncongruent CSMs in CSM ⋆ ( A , B ) \operatorname{CSM}^{\star}(A,B) CSM ⋆ ( A , B ) that have ( L ~ A , L ~ B , S ) (\widetilde{L}_{A},\widetilde{L}_{B},S) ( L A , L B , S ) . Among them, each J p , t 1 , t 2 , … , t Z ~ \mathcal{J}_{p,t_{1},t_{2},\ldots,t_{\widetilde{Z}}} J p , t 1 , t 2 , … , t Z is congruent to a J p , 0 , t 2 ′ , … , t Z ~ ′ \mathcal{J}_{p,0,t'_{2},\ldots,t'_{\widetilde{Z}}} J p , 0 , t 2 ′ , … , t Z ′ , where t i ′ = t i − t 1 t'_{i}=t_{i}-t_{1} t i ′ = t i − t 1 . Since p p p can take only a finite number of values, there are infinitely many PCTs having the same p p p and different ( 0 , t 2 ′ , … , t Z ~ ′ ) (0,t'_{2},\ldots,t'_{\widetilde{Z}}) ( 0 , t 2 ′ , … , t Z ′ ) that satisfy
d ( J p , 0 , t 2 ′ , … , t Z ~ ′ ) ≤ d max . (75) d(\mathcal{J}_{p,0,t'_{2},\ldots,t'_{\widetilde{Z}}})\le d_{\max}. \tag*{(75)} d ( J p , 0 , t 2 ′ , … , t Z ′ ) ≤ d m a x . (75)
These ( 0 , t 2 ′ , … , t Z ~ ′ ) (0,t'_{2},\ldots,t'_{\widetilde{Z}}) ( 0 , t 2 ′ , … , t Z ′ ) form an infinite subset of L ~ B Z ~ \widetilde{L}_{B}^{\widetilde{Z}} L B Z , so there exist j j j such that ∣ t j ′ ∣ |t'_{j}| ∣ t j ′ ∣ is unbounded; otherwise, the subset would be finite. Let
y = ∣ b ~ p ( j ) + t j ′ − b ~ p ( 1 ) − a ~ j + a ~ 1 ∣ , (76) y=\left|\widetilde{b}_{p(j)}+t'_{j}-\widetilde{b}_{p(1)}-\widetilde{a}_{j}+\widetilde{a}_{1}\right|, \tag*{(76)} y = b p ( j ) + t j ′ − b p ( 1 ) − a j + a 1 , (76)
which is also unbounded. We have
[ d ( J p , 0 , t 2 ′ , … , t Z ~ ′ ) ] ℓ = min τ ∈ R 3 ∑ i = 1 Z ~ θ i ∣ b ~ p ( i ) + t i ′ + τ − a ~ i ∣ ℓ (77) \left[d(\mathcal{J}_{p,0,t'_{2},\ldots,t'_{\widetilde{Z}}})\right]^{\ell}=\min_{\tau\in\mathbb{R}^{3}}\sum_{i=1}^{\widetilde{Z}}\theta_{i}\left|\widetilde{b}_{p(i)}+t'_{i}+\tau-\widetilde{a}_{i}\right|^{\ell} \tag*{(77)} [ d ( J p , 0 , t 2 ′ , … , t Z ′ ) ] ℓ = τ ∈ R 3 min i = 1 ∑ Z θ i b p ( i ) + t i ′ + τ − a i ℓ (77)
≥ min τ ∈ R 3 ( θ 1 ∣ b ~ p ( 1 ) + τ − a ~ 1 ∣ ℓ + θ j ∣ b ~ p ( j ) + t j ′ + τ − a ~ j ∣ ℓ ) (78) \ge\min_{\tau\in\mathbb{R}^{3}}\left(\theta_{1}\left|\widetilde{b}_{p(1)}+\tau-\widetilde{a}_{1}\right|^{\ell}+\theta_{j}\left|\widetilde{b}_{p(j)}+t'_{j}+\tau-\widetilde{a}_{j}\right|^{\ell}\right) \tag*{(78)} ≥ τ ∈ R 3 min ( θ 1 b p ( 1 ) + τ − a 1 ℓ + θ j b p ( j ) + t j ′ + τ − a j ℓ ) (78)
= min τ ∈ R 3 ( θ 1 ∣ b ~ p ( 1 ) + τ − a ~ 1 ∣ ℓ + θ j ∣ ( b ~ p ( 1 ) + τ − a ~ 1 ) + ( b ~ p ( j ) + t j ′ − b ~ p ( 1 ) − a ~ j + a ~ 1 ) ∣ ℓ ) (79) =\min_{\tau\in\mathbb{R}^{3}}\left(\theta_{1}\left|\widetilde{b}_{p(1)}+\tau-\widetilde{a}_{1}\right|^{\ell}+\theta_{j}\left|\left(\widetilde{b}_{p(1)}+\tau-\widetilde{a}_{1}\right)+\left(\widetilde{b}_{p(j)}+t'_{j}-\widetilde{b}_{p(1)}-\widetilde{a}_{j}+\widetilde{a}_{1}\right)\right|^{\ell}\right) \tag*{(79)} = τ ∈ R 3 min ( θ 1 b p ( 1 ) + τ − a 1 ℓ + θ j ( b p ( 1 ) + τ − a 1 ) + ( b p ( j ) + t j ′ − b p ( 1 ) − a j + a 1 ) ℓ ) (79)
≥ min τ ∈ R 3 ( θ 1 ∣ b ~ p ( 1 ) + τ − a ~ 1 ∣ ℓ + θ j ∣ ∣ b ~ p ( 1 ) + τ − a ~ 1 ∣ − ∣ b ~ p ( j ) + t j ′ − b ~ p ( 1 ) − a ~ j + a ~ 1 ∣ ∣ ℓ ) (80) \ge\min_{\tau\in\mathbb{R}^{3}}\left(\theta_{1}\left|\widetilde{b}_{p(1)}+\tau-\widetilde{a}_{1}\right|^{\ell}+\theta_{j}\left|\left|\widetilde{b}_{p(1)}+\tau-\widetilde{a}_{1}\right|-\left|\widetilde{b}_{p(j)}+t'_{j}-\widetilde{b}_{p(1)}-\widetilde{a}_{j}+\widetilde{a}_{1}\right|\right|^{\ell}\right) \tag*{(80)} ≥ τ ∈ R 3 min ( θ 1 b p ( 1 ) + τ − a 1 ℓ + θ j b p ( 1 ) + τ − a 1 − b p ( j ) + t j ′ − b p ( 1 ) − a j + a 1 ℓ ) (80)
= min x ≥ 0 ( θ 1 x ℓ + θ j ∣ x − y ∣ ℓ ) = { y min { θ 1 , θ j } , if ℓ = 1 , y ℓ ( θ 1 − 1 ℓ − 1 + θ j − 1 ℓ − 1 ) − ( ℓ − 1 ) , if ℓ > 1. (81) =\min_{x\ge0}\left(\theta_{1}x^{\ell}+\theta_{j}|x-y|^{\ell}\right)=
\begin{cases}
y\min\{\theta_{1},\theta_{j}\}, & \text{if }\ell=1,\\
y^{\ell}\left(\theta_{1}^{-\frac{1}{\ell-1}}+\theta_{j}^{-\frac{1}{\ell-1}}\right)^{-(\ell-1)}, & \text{if }\ell>1.
\end{cases} \tag*{(81)} = x ≥ 0 min ( θ 1 x ℓ + θ j ∣ x − y ∣ ℓ ) = ⎩ ⎨ ⎧ y min { θ 1 , θ j } , y ℓ ( θ 1 − ℓ − 1 1 + θ j − ℓ − 1 1 ) − ( ℓ − 1 ) , if ℓ = 1 , if ℓ > 1. (81)
Since y y y is unbounded, Eq. (81) can be arbitrarily large, which contradicts Eq. (75) .
Theorem 9. The number of noncongruent CSMs in C S M ⋆ ( A , B ) \mathrm{CSM}^{\star}(\mathcal{A},\mathcal{B}) CSM ⋆ ( A , B ) is finite regardless of μ max \mu_{\max} μ m a x , w max w_{\max} w m a x , and d max d_{\max} d m a x .
Proof. Replace the root node “all CSMs” in Figure 2 with “all noncongruent CSMs”. Theorems 7 and 8 ensure that the breadth of the pruned tree is finite at each level. ■
Algorithms
To enumerate all noncongruent CSMs in C S M ⋆ ( A , B ) \mathrm{CSM}^{\star}(\mathcal{A},\mathcal{B}) CSM ⋆ ( A , B ) , Theorem 4 allows us to enumerate all noncongruent SLMs in S L M ⋆ ( A , B ) \mathrm{SLM}^{\star}(\mathcal{A},\mathcal{B}) SLM ⋆ ( A , B ) first, and then all noncongruent CSMs within each SLM. With Theorems 5 and 6, we only need to generate a complete subset of
I M T ⋆ ( μ ) = { ( H A , H B , Q ) ∈ I M T ( μ ) | w ( C B H B Q H A − 1 C A − 1 ) ≤ w max } (82) \mathrm{IMT}^{\star}(\mu)=\left\{(H_A,H_B,Q)\in\mathrm{IMT}(\mu)\ \middle|\ w(C_BH_BQH_A^{-1}C_A^{-1})\leq w_{\max}\right\} \tag*{(82)} IMT ⋆ ( μ ) = { ( H A , H B , Q ) ∈ IMT ( μ ) w ( C B H B Q H A − 1 C A − 1 ) ≤ w m a x } (82)
for μ = 1 , … , μ max \mu=1,\ldots,\mu_{\max} μ = 1 , … , μ m a x , and a complete subset of
P C T ⋆ ( L ~ A , L ~ B , S ) = { ( p , t 1 , … , t Z ~ ) ∈ P C T ( L ~ A , L ~ B , S ) | d ( J p , t 1 , … , t Z ~ ) ≤ d max } (83) \mathrm{PCT}^{\star}(\widetilde{L}_A,\widetilde{L}_B,S)=\left\{(p,t_1,\ldots,t_{\widetilde{Z}})\in\mathrm{PCT}(\widetilde{L}_A,\widetilde{L}_B,S)\ \middle|\ d(J_{p,t_1,\ldots,t_{\widetilde{Z}}})\leq d_{\max}\right\} \tag*{(83)} PCT ⋆ ( L A , L B , S ) = { ( p , t 1 , … , t Z ) ∈ PCT ( L A , L B , S ) d ( J p , t 1 , … , t Z ) ≤ d m a x } (83)
for each ( L ~ A , L ~ B , S ) ∈ S L M ⋆ ( A , B ; μ ) (\widetilde{L}_A,\widetilde{L}_B,S)\in\mathrm{SLM}^{\star}(\mathcal{A},\mathcal{B};\mu) ( L A , L B , S ) ∈ SLM ⋆ ( A , B ; μ ) .
In this section, we will introduce Algorithm 1 for IMTs as well as Algorithms 2 and 3 for PCTs, and then apply them on some typical SSPTs. These algorithms do not involve electronic structure or atomic force field calculations, i.e., they are purely geometric. The pseudocodes are presented in an easy-to-understand form, but the actual implementation can be more efficient, e.g., all loops in Algorithm 1 can be parallelized.
Enumerating sublattice matches
Let’s first consider how to produce the entire I M T ⋆ ( μ ) \mathrm{IMT}^{\star}(\mu) IMT ⋆ ( μ ) rather than its complete subset. It is easy to enumerate all possible values of H A H_A H A and H B H_B H B , so the difficulty lies solely in computing all possible Q Q Q for a given HNF pair ( H A , H B ) (H_A,H_B) ( H A , H B ) , i.e., producing { Q ∣ ( H A , H B , Q ) ∈ I M T ⋆ ( μ ) } \{Q\mid(H_A,H_B,Q)\in\mathrm{IMT}^{\star}(\mu)\} { Q ∣ ( H A , H B , Q ) ∈ IMT ⋆ ( μ )} , which we denote by { Q } \{Q\} { Q } for simplicity. To this end, we first sample the 9D region
Ω S 0 = { S 0 ∈ R 3 × 3 | w ( S 0 ) ≤ w max } (84) \Omega_{S_0}=\left\{S_0\in\mathbb{R}^{3\times3}\ \middle|\ w(S_0)\leq w_{\max}\right\} \tag*{(84)} Ω S 0 = { S 0 ∈ R 3 × 3 w ( S 0 ) ≤ w m a x } (84)
producing a finite set consisting of trial matrices, denoted as { S 0 } ⊂ Ω S 0 \{S_0\}\subset\Omega_{S_0} { S 0 } ⊂ Ω S 0 . Then, for each trial matrix S 0 S_0 S 0 , we compute the closest IMTs by (1) substituting S 0 S_0 S 0 into (51) , (2) solve for Q Q Q for each pair ( H A , H B ) (H_A,H_B) ( H A , H B ) , and (3) round each matrix element of Q Q Q to the nearest integer. In other words, we apply the linear mapping
ϕ H A , H B : R 3 × 3 → R 3 × 3 , (85) \phi_{H_A,H_B}:\mathbb{R}^{3\times3}\to\mathbb{R}^{3\times3}, \tag*{(85)} ϕ H A , H B : R 3 × 3 → R 3 × 3 , (85)
S 0 ↦ H B − 1 C B − 1 S 0 C A H A , (86) S_0\mapsto H_B^{-1}C_B^{-1}S_0C_AH_A, \tag*{(86)} S 0 ↦ H B − 1 C B − 1 S 0 C A H A , (86)
To the set { S 0 } \{S_0\} { S 0 } . As long as { S 0 } \{S_0\} { S 0 } is sampled dense enough, its image under ϕ H A , H B \phi_{H_A,H_B} ϕ H A , H B will intersect each Q Q Q ’s “preimage of rounding”
round − 1 ( Q ) = { Q + X | X ∈ ( − 1 2 , 1 2 ) 3 × 3 } , (87) \operatorname{round}^{-1}(Q)=\left\{Q+X\ \middle|\ X\in\left(-\frac{1}{2},\frac{1}{2}\right)^{3\times3}\right\}, \tag*{(87)} round − 1 ( Q ) = { Q + X X ∈ ( − 2 1 , 2 1 ) 3 × 3 } , (87)
a 9D hypercube centered at Q Q Q [Fig. 7(b)]. In that case, we can extract { Q } \{Q\} { Q } from round [ ϕ H A , H B ( { S 0 } ) ] \operatorname{round}[\phi_{H_A,H_B}(\{S_0\})] round [ ϕ H A , H B ({ S 0 })] .
The only remaining problem is how to tell whether the set { S 0 } \{S_0\} { S 0 } is dense enough such that { Q } \{Q\} { Q } is covered by its image under ϕ H A , H B \phi_{H_A,H_B} ϕ H A , H B . Our approach is to generate S 0 S_0 S 0 one by one until i t h i_{\mathrm{th}} i th consecutive iterations fail to produce any new IMT, as described in Algorithm 1. The value of i t h i_{\mathrm{th}} i th can be derived by hypothesis testing. Whenever the algorithm starts or a new IMT is produced, we initiate a test of the two opposing hypotheses, namely
H 0 H_0 H 0 : The current myimts is complete,
H 1 H_1 H 1 : The current myimts is incomplete.
Then, when we perform i i i iterations without producing any new IMT, the conditional probability of this event under H 0 H_0 H 0 is 1, whereas under H 1 H_1 H 1 it is only
Pr ( i ∣ H 1 ) ≤ ( 1 − η ) i , (88) \Pr(i\mid H_1)\leq(1-\eta)^i, \tag*{(88)} Pr ( i ∣ H 1 ) ≤ ( 1 − η ) i , (88)
where η \eta η denotes the minimum probability of a given IMT being generated in a single iteration. If one would reject H 1 H_1 H 1 when Pr ( i ∣ H 1 ) < ϵ \Pr(i\mid H_1)<\epsilon Pr ( i ∣ H 1 ) < ϵ , it is sufficient to set
i t h = ln ϵ ln ( 1 − η ) . (89) i_{\mathrm{th}}=\frac{\ln\epsilon}{\ln(1-\eta)}. \tag*{(89)} i th = ln ( 1 − η ) ln ϵ . (89)
Algorithm 1. Listing all noncongruent IMTs
Input: $C_A$, $C_B$, $Z_A$, $Z_B$, $\mu$, $w_{\max}$
initialize myimts $\leftarrow \{\}$; $i \leftarrow 0$
while $i \le i_{\mathrm{th}}$ do
generate a random $S_0 \in \Omega_{S_0}$
foreach $H_A \in \operatorname{HNF}\left(\frac{\mu\operatorname{lcm}(Z_A,Z_B)}{Z_A}\right)$ do
foreach $H_B \in \operatorname{HNF}\left(\frac{\mu\operatorname{lcm}(Z_A,Z_B)}{Z_B}\right)$ do
$Q \leftarrow \operatorname{round}(H_B^{-1}C_B^{-1}S_0C_AH_A)$
$S \leftarrow C_BH_BQH_A^{-1}C_A^{-1}$
if $Q \in \operatorname{GL}(3,\mathbb{Z})$ and $w(S) \le w_{\max}$ then
$x \leftarrow \operatorname{Standardize}(H_A,H_B,Q)$
if $x \notin$ myimts then
add $x$ to myimts
$i \leftarrow 0$
else $i \leftarrow i+1$
return myimts
Note that the probability ϵ \epsilon ϵ of incorrectly asserting completeness decreases exponentially with increasing i t h i_{\mathrm{th}} i th . In this sense, we claim that Algorithm 1 is essentially an exhaustive search algorithm.
Recall that our goal is to list all noncongruent elements in I M T ⋆ ( μ ) \mathrm{IMT}^{\star}(\mu) IMT ⋆ ( μ ) . We can treat each IMT as its congruence class—whenever an IMT is generated, if it is congruent to some element already in myimts, it is considered not new and i i i increases. However, a better way might be using a Standardize() function to convert each IMT into the representative of its congruence class (e.g., the lexicographically smallest one), as shown in the pseudocode. Either way will replace 1 − η 1-\eta 1 − η in Eq. (89) with the minimum probability that no IMT from a given congruence class is generated in a single iteration. A conservative estimate of i t h i_{\mathrm{th}} i th is provided in Appendix B, while in practice, i t h i_{\mathrm{th}} i th can be dynamically adjusted to accelerate the algorithm.
Enumerating shuffles
To list all noncongruent PCTs, Algorithm 2 involves three functions: (1) OptimizePCT() for finding the PCT with the minimum d d d , (2) Fill() for generating all noncongruent PCTs with a given p p p , and (3) Split() for excluding previously enumerated values of p p p . All we need to do is to iteratively invoke them, as shown in Figure 8 . Next, we will introduce the specific algorithms for implementing these three functions separately.
Figure 8. A schematic diagram showing how Algorithm 2 works, where each point represents a PCT. First, OptimizePCT() is invoked to obtain the PCT with the smallest d d d . Then, Fill() generates all PCTs that share the same permutation with it, while Split() produces a set of constraints to disable this permutation in subsequent computations. By passing these constraints as parameters to OptimizePCT(), other bottom PCTs (dots in blue circles) can be generated.
We use OptimizePCT(constraint) to generate the PCT with the smallest d d d under the constraints specified by constraint. In each iteration step, the overall translation τ \tau τ is fixed, and the best translation t i j ∈ L ~ B t_{ij} \in\widetilde{L}_B t ij ∈ L B for each atom pair ( a i , b j ) (a_i,b_j) ( a i , b j ) is computed. Then, the best permutation p p p under this τ \tau τ is determined using BestAssignment() (e.g., the Jonker-Volgenant algorithm [45 , 46 ] ), so that
Algorithm 2. Listing all noncongruent PCTs
Input: $A$, $B$, $(\widetilde{L}_A,\widetilde{L}_B,S)$, $d_{\max}$
initialize mypcts $\leftarrow \{\}$; myconstraints $\leftarrow$ empty queue
enqueue $\{\}$ to myconstraints
while myconstraints is not empty do
dequeue constraint from myconstraints
$d,(p,t_1,\ldots,t_{\widetilde{Z}}) \leftarrow \operatorname{OptimizePCT}(\mathrm{constraint})$
if $d \le d_{\max}$ then
foreach $(t'_2,\ldots,t'_{\widetilde{Z}}) \in \operatorname{Fill}(p)$ do
add $(p,0,t'_2,\ldots,t'_{\widetilde{Z}})$ to mypcts
foreach newcons $\in \operatorname{Split}(\mathrm{constraint},p)$ do
enqueue newcons to myconstraints
return mypcts
t 1 , … , t Z ~ t_1,\ldots,t_{\widetilde{Z}} t 1 , … , t Z and
d ^ 0 ( τ ) = min p , t 1 , … , t Z ~ d ^ [ ( + τ ) ∘ J p , t 1 , … , t Z ~ ] (90) \widehat{d}_0(\tau)=\min_{p,t_1,\ldots,t_{\widetilde{Z}}}\widehat{d}\left[(+\tau)\circ\mathcal{J}_{p,t_1,\ldots,t_{\widetilde{Z}}}\right] \tag*{(90)} d 0 ( τ ) = p , t 1 , … , t Z min d [ ( + τ ) ∘ J p , t 1 , … , t Z ] (90)
are also obtained. This process is iterated with different τ \tau τ values until the global minimum of d ^ 0 ( τ ) \widehat{d}_0(\tau) d 0 ( τ ) is found, where strategies such as basin-hopping are employed [47 ] . The final iteration uses τ ⋆ = argmin τ d ^ 0 ( τ ) \tau^\star=\operatorname*{argmin}_{\tau}\widehat{d}_0(\tau) τ ⋆ = argmin τ d 0 ( τ ) , at which point the PCT given by BestAssignment() is
argmin p , t 1 , … , t Z ~ d ^ [ ( + τ ⋆ ) ∘ J p , t 1 , … , t Z ~ ] (91) \operatorname*{argmin}_{p,t_1,\ldots,t_{\widetilde{Z}}}\widehat{d}\left[(+\tau^\star)\circ\mathcal{J}_{p,t_1,\ldots,t_{\widetilde{Z}}}\right] \tag*{(91)} p , t 1 , … , t Z argmin d [ ( + τ ⋆ ) ∘ J p , t 1 , … , t Z ] (91)
= argmin p , t 1 , … , t Z ~ min τ ∈ R 3 d ^ [ ( + τ ) ∘ J p , t 1 , … , t Z ~ ] (92) =\operatorname*{argmin}_{p,t_1,\ldots,t_{\widetilde{Z}}}\min_{\tau\in\mathbb{R}^3}\widehat{d}\left[(+\tau)\circ\mathcal{J}_{p,t_1,\ldots,t_{\widetilde{Z}}}\right] \tag*{(92)} = p , t 1 , … , t Z argmin τ ∈ R 3 min d [ ( + τ ) ∘ J p , t 1 , … , t Z ] (92)
= argmin p , t 1 , … , t Z ~ d ( J p , t 1 , … , t Z ~ ) , (93) =\operatorname*{argmin}_{p,t_1,\ldots,t_{\widetilde{Z}}}d(\mathcal{J}_{p,t_1,\ldots,t_{\widetilde{Z}}}), \tag*{(93)} = p , t 1 , … , t Z argmin d ( J p , t 1 , … , t Z ) , (93)
which is exactly what we need.
To formalize this idea and handle atomic species, the pseudocode is presented in Algorithm 3. The function Motifs(L ~ A , L ~ B , S \widetilde{L}_A,\widetilde{L}_B,S L A , L B , S ) is a mapping like Eq. (59) but also sorts the atoms by atomic species, where n n n denotes the
Algorithm 3. Optimizing PCT under a given constraint (producing the PCT with least shuffle distance)
Input: constraint, and all inputs of Algorithm 2
a_1^{(1)}, \cdots, a_{\tilde Z_1}^{(1)}, a_1^{(2)}, \cdots, a_{\tilde Z_2}^{(2)}, \cdots, a_1^{(n)}, \cdots, a_{\tilde Z_n}^{(n)}, b_1^{(1)}, \cdots, b_{\tilde Z_1}^{(1)}, b_1^{(2)}, \cdots, b_{\tilde Z_2}^{(2)}, \cdots, b_1^{(n)}, \cdots, b_{\tilde Z_n}^{(n)} \leftarrow \operatorname{Motifs}(\tilde L_A,\tilde L_B,S)
def ShuffleDistance(\tau, \operatorname{returnpct}=false)
for \alpha=1 to n do
for i=1 to \tilde Z_\alpha do
for j=1 to \tilde Z_\alpha do
t_{ij}^{(\alpha)} \leftarrow \underset{t\in \tilde L_B}{\operatorname{argmin}}\left|\tilde b_j^{(\alpha)}+\tilde t+\tau-\tilde a_i^{(\alpha)}\right|^\ell;
D_{ij}^{(\alpha)}\leftarrow\left|\tilde b_j^{(\alpha)}+\tilde t_{ij}^{(\alpha)}+\tau-\tilde a_i^{(\alpha)}\right|^\ell
p^{(\alpha)}\leftarrow \operatorname{BestAssignment}(D^{(\alpha)},\operatorname{constraint});
for i=1 to \tilde Z_\alpha do t_i^{(\alpha)}\leftarrow t_{i,p^{(\alpha)}(i)}^{(\alpha)}
d\leftarrow\left(\sum_{\alpha=1}^{n}\sum_{i=1}^{\tilde Z_\alpha}\theta_i^{(\alpha)}D_{i,p^{(\alpha)}(i)}^{(\alpha)}\right)^{1/\ell}
if returnpct then return d,\left((p^{(1)}|p^{(2)}|\cdots|p^{(n)}),t_1^{(1)},\cdots,t_{\tilde Z_1}^{(1)},t_1^{(2)},\cdots,t_{\tilde Z_2}^{(2)},\cdots,t_1^{(n)},\cdots,t_{\tilde Z_n}^{(n)}\right)
else return d
\tau^*\leftarrow\underset{\tau\in\mathbb R^3}{\operatorname{argmin}}\operatorname{ShuffleDistance}(\tau);
return \operatorname{ShuffleDistance}(\tau^*,\operatorname{returnpct}=true)
number of atomic species in the initial and final structures, Z ~ α \tilde Z_\alpha Z ~ α denotes the number of atoms with the α \alpha α -th species, and other variables related to the α \alpha α -th atomic species are denoted with superscripts as a i ( α ) \mathbf{a}_i^{(\alpha)} a i ( α ) . The function BestAssignment ( D , constraint ) \operatorname{BestAssignment}(D,\operatorname{constraint}) BestAssignment ( D , constraint ) returns a permutation p p p that minimizes ∑ i D i , p ( i ) \sum_i D_{i,p(i)} ∑ i D i , p ( i ) , where D D D is the cost matrix and constraint is a set of the form
{ ( i , j ) , ( i ′ , j ′ ) , ⋯ ; ( k , l ) , ( k ′ , l ′ ) , ⋯ } , (94) \left\{(i,j),(i',j'),\cdots;(k,l),(k',l'),\cdots\right\}, \tag*{(94)} { ( i , j ) , ( i ′ , j ′ ) , ⋯ ; ( k , l ) , ( k ′ , l ′ ) , ⋯ } , (94)
where ( i , j ) (i,j) ( i , j ) means enforcing p ( i ) = j p(i)=j p ( i ) = j , and $(k,l) means requiring p ( k ) ≠ l p(k)\ne l p ( k ) = l [48 ] . The correspondence of each atomic species is optimized separately and then combined into a single PCT, where ( p ( 1 ) ∣ p ( 2 ) ∣ ⋯ ∣ p ( n ) ) ∈ Sym ( Z ~ ) (p^{(1)}|p^{(2)}|\cdots|p^{(n)})\in\operatorname{Sym}(\tilde Z) ( p ( 1 ) ∣ p ( 2 ) ∣ ⋯ ∣ p ( n ) ) ∈ Sym ( Z ~ ) represents performing n n n permutations separately within n n n atomic species.
We say that ( p , t 1 , ⋯ , t Z ~ ) (p,t_1,\cdots,t_{\tilde Z}) ( p , t 1 , ⋯ , t Z ~ ) is a bottom PCT if its d d d is the smallest among all PCTs with the same permutation. Whenever we obtain a bottom PCT, we invoke Fill ( p ) \operatorname{Fill}(p) Fill ( p ) to list all PCTs of the form ( p , 0 , t 2 ′ , ⋯ , t Z ~ ′ ) (p,0,t'_2,\cdots,t'_{\tilde Z}) ( p , 0 , t 2 ′ , ⋯ , t Z ~ ′ ) that satisfy Eq. (75) . Here, we have let t 1 ′ = 0 t'_1=0 t 1 ′ = 0 to make the number of PCTs finite without loss of completeness (see the proof of Lemma 8). Since v i = b ~ p ( i ) − a ~ i \mathbf v_i=\tilde{\mathbf b}_{p(i)}-\tilde{\mathbf a}_i v i = b ~ p ( i ) − a ~ i is constant during each invocation of Fill ( ) \operatorname{Fill}() Fill ( ) , one may simply use a flood fill algorithm to produce
{ ( t 2 ′ , ⋯ , t Z ~ ′ ) ∈ L ~ B Z ~ − 1 | min τ ∈ R 3 ∑ i = 1 Z ~ θ i ∣ v i + t ~ i + τ ∣ ℓ ≤ d max ℓ } . (95) \left\{(t'_2,\cdots,t'_{\tilde Z})\in\tilde L_B^{\tilde Z-1}\ \middle|\ \min_{\tau\in\mathbb R^3}\sum_{i=1}^{\tilde Z}\theta_i\left|\mathbf v_i+\tilde{\mathbf t}_i+\tau\right|^\ell\le d_{\max}^{\ell}\right\}. \tag*{(95)} ⎩ ⎨ ⎧ ( t 2 ′ , ⋯ , t Z ~ ′ ) ∈ L ~ B Z ~ − 1 τ ∈ R 3 min i = 1 ∑ Z ~ θ i v i + t ~ i + τ ℓ ≤ d m a x ℓ ⎭ ⎬ ⎫ . (95)
When ℓ = 2 \ell=2 ℓ = 2 , Lemma 8 implies that ( t 2 , ⋯ , t Z ~ ′ ) (t_2,\cdots,t'_{\tilde Z}) ( t 2 , ⋯ , t Z ~ ′ ) takes values in a known hyperellipsoid so that one may employ a more efficient algorithm.
The last function Split ( constraint , p ) \operatorname{Split}(\operatorname{constraint},p) Split ( constraint , p ) excludes the solution p p p by splitting the assignment problem that satisfies constraint into several subproblems, which was originally proposed in Ref. 48. It incorporates “excluding p p p ” into constraint by returning Z ~ − 1 \tilde Z-1 Z ~ − 1 mutually disjoint sets
constraint ∪ { ( 1 , p ( 1 ) ) ‾ } , (96) \operatorname{constraint}\cup\left\{\overline{(1,p(1))}\right\}, \tag*{(96)} constraint ∪ { ( 1 , p ( 1 )) } , (96)
constraint ∪ { ( 1 , p ( 1 ) ) ; ( 2 , p ( 2 ) ) ‾ } , (97) \operatorname{constraint}\cup\left\{\overline{(1,p(1));(2,p(2))}\right\}, \tag*{(97)} constraint ∪ { ( 1 , p ( 1 )) ; ( 2 , p ( 2 )) } , (97)
constraint ∪ { ( 1 , p ( 1 ) ) , ( 2 , p ( 2 ) ) ; ( 3 , p ( 3 ) ) ‾ } , \operatorname{constraint}\cup\left\{(1,p(1)),(2,p(2));\overline{(3,p(3))}\right\}, constraint ∪ { ( 1 , p ( 1 )) , ( 2 , p ( 2 )) ; ( 3 , p ( 3 )) } ,
⋯ \cdots ⋯
constraint ∪ { ( 1 , p ( 1 ) ) , ⋯ , ( Z ~ − 2 , p ( Z ~ − 2 ) ) ; ( Z ~ − 1 , p ( Z ~ − 1 ) ) ‾ } . (98) \operatorname{constraint}\cup\left\{(1,p(1)),\cdots,(\tilde Z-2,p(\tilde Z-2));\overline{(\tilde Z-1,p(\tilde Z-1))}\right\}. \tag*{(98)} constraint ∪ { ( 1 , p ( 1 )) , ⋯ , ( Z ~ − 2 , p ( Z ~ − 2 )) ; ( Z ~ − 1 , p ( Z ~ − 1 )) } . (98)
This partitions all feasible solutions that satisfy constraint and are not p p p . If a set contains incompatible requirements, such as ( i , j ) (i,j) ( i , j ) and ( i , j ) (i,j) ( i , j ) , it will be discarded. In Algorithm 2, whenever we obtain a bottom PCT, at most Z ~ − 1 \tilde Z-1 Z ~ − 1 sets like Eq. (96) are enqueued to myconstraints, each of which can yield a different bottom PCT via OptimizePCT ( ) \operatorname{OptimizePCT}() OptimizePCT ( ) .
It should be noted that mypcts produced by Algorithm 2 is overcomplete—its elements are not noncongruent but rather appear in equivalence classes. This is because for any t A ∈ L A t_A\in L_A t A ∈ L A and t B ∈ L B t_B\in L_B t B ∈ L B , we have ( + t B ) ∘ J ∘ ( − t A ) (+t_B)\circ\mathcal J\circ(-t_A) ( + t B ) ∘ J ∘ ( − t A ) congruent to J \mathcal J J , and their PCTs generally have different permutations unless t B − S t A ∈ L ~ B t_B-\mathcal S t_A\in\tilde L_B t B − S t A ∈ L ~ B . One may eliminate this redundancy by additionally invoking Split ( ) \operatorname{Split}() Split ( ) to all “congruent” permutations, which is omitted here for brevity. Another point to note is that a PCT generated by Algorithm 2 or 3 may represent a CSM whose SMI is not ( L ~ A , L ~ B , S ) (\tilde L_A,\tilde L_B,S) ( L ~ A , L ~ B , S ) , but rather ( L ~ A ′ , L ~ B ′ , S ) (\tilde L'_A,\tilde L'_B,S) ( L ~ A ′ , L ~ B ′ , S ) , where L ~ A ′ ⊃ L ~ A \tilde L'_A\supset\tilde L_A L ~ A ′ ⊃ L ~ A and L ~ B ′ ⊃ L ~ B \tilde L'_B\supset\tilde L_B L ~ B ′ ⊃ L ~ B are finer lattices. This can only happen when S L ~ A = L ~ B \mathcal S\tilde L_A=\tilde L_B S L ~ A = L ~ B is a proper subset of S L A ∩ L B S L_A\cap L_B S L A ∩ L B , and is a direct consequence of the fact that the PCT representation does not forbid shuffles with shuffle lattices finer than L ~ B \tilde L_B L ~ B . However, this feature is useful in practical applications (see § 3 A) and does not affect the completeness of the enumeration.
Application
In this section, we demonstrate the applications of Algorithms 1–3 through case studies of the B1–B2 and graphite-to-diamond transitions. For implementation details, see our Python package CRYSTMATCH [49 ] , which utilizes SPGLIB for symmetry detection [50 ] . We will see that the enumeration range easily covers and goes beyond previously proposed SSPT mechanisms. The resulting database can be further analyzed from multiple perspectives, or used as inputs to NEB-like methods.
Orientation relationship analysis
As one of the simplest SSPTs in compounds, the B1–B2 transition is similar to the FCC-to-BCC transition, but involves two atomic species. Multiple distinct mechanisms—i.e., CSMs—have been proposed [27 ] , including the purely distortive (d = 0 d = 0 d = 0 ) Buerger one [33 ] , the Watanabe-Tokonami-Morimoto (WTM) one which can explain the observed orientation relationship (OR) [36 ] , and the Tolédano-Knorr-Ehm-Depmeier (TKED) one which is supported by MetaD simulations involving ∼ 10 4 \sim10^4 ∼ 1 0 4 atoms [8 , 38 ] . Recently, the Therrien-Graf-Stevanović (TGS) mechanism was identified using the P2PTRANS method [25 ] , which has a significantly lower strain. These CSMs and their evidence are summarized in Table II .
A CSM can be decomposed into an SLM and a PCT, where the former consists of a deformation gradient S S S and a shuffle lattice. Among these components, the S S S alone determines the OR and the habit plane, and can thus be compared directly with experimental observations. In contrast, the shuffle lattice and the PCT describe microscopic details that are, currently, accessible only through simulations. In this sense, listing all possible S S S is of broader interest, which can be achieved using Algorithm 1. To further characterize S S S from a CSM perspective, we used Algorithm 3 to compute the minimal multiplicity and minimal shuffle distance among all CSMs with deformation gradient S S S , denoted by μ 0 ( S ) \mu_0(S) μ 0 ( S ) and d 0 ( S ) d_0(S) d 0 ( S ) , respectively. For simplicity, we let ℓ = 2 \ell= 2 ℓ = 2 and assign equal shuffle-distance weights to Cs and Cl atoms, i.e., set θ i \theta_i θ i as a constant. A more physical choice of weights will be discussed in § 3 B.
As a preliminary investigation, we enumerated all SLMs for the B1–B2 transition with multiplicity μ ≤ 6 \mu\le6 μ ≤ 6 (i.e., period Z ~ ≤ 12 \widetilde{Z} \le12 Z ≤ 12 ) and RMSS
ε ˉ ( S ) = 1 3 ∑ i = 1 3 [ σ i ( S ) − 1 ] 2 (99) \bar{\varepsilon}(S) = \sqrt{\frac{1}{3}\sum_{i=1}^{3}[\sigma_i(S)-1]^2} \tag*{(99)} ε ˉ ( S ) = 3 1 i = 1 ∑ 3 [ σ i ( S ) − 1 ] 2 (99)
less than 30%. This was achieved by replacing Ω S 0 \Omega_{S_0} Ω S 0 in Algorithm 1 with { S ∈ R 3 × 3 ∣ ε ˉ ( S ) ≤ 0.3 } \{S \in\mathbb{R}^{3\times3} \mid\bar{\varepsilon}(S) \le0.3\} { S ∈ R 3 × 3 ∣ ε ˉ ( S ) ≤ 0.3 } . From the enumeration result, we identified the SLMs of all established CSMs above, as shown in Figure 9 (a). A total of 788 noncongruent SLMs with 393 distinct deformation
Figure 9. All deformation gradients S S S with μ 0 ≤ 6 \mu_0 \le6 μ 0 ≤ 6 and ε ˉ ≤ 30 % \bar{\varepsilon} \le30\% ε ˉ ≤ 30% . Each point represents a unique S S S , whose shape indicates its μ 0 \mu_0 μ 0 . (a) Each S S S is colored according to its estimated strain energy density w ( S ) w(S) w ( S ) . Those S S S of previously proposed mechanisms are pointed out by gray solid lines, where the WTM one and TKED one share the same S S S , and the TGS one has the lowest w w w among all S S S enumerated. (b)(c) Each S S S is colored according to its deviation angles φ 1 \varphi_1 φ 1 from the WB OR and φ 2 \varphi_2 φ 2 from the OFO OR. Those S S S with strictly φ 1 = 0 \varphi_1 = 0 φ 1 = 0 or φ 2 = 0 \varphi_2 = 0 φ 2 = 0 are highlighted in blue.
gradients are produced, taking 1 min 11 s on a single core of a Mac M1 chip. The subsequent d 0 d_0 d 0 calculation took only 13 s, producing 393 CSMs with the smallest d d d among all CSMs sharing their respective deformation gradients, i.e., satisfying
d ( J ) = d 0 ( S ) . (100) d(\mathcal{J}) = d_0(S). \tag*{(100)} d ( J ) = d 0 ( S ) . (100)
We refer to a CSM with this property as a representative CSM, whose PCT is necessarily a bottom PCT, though the converse does not hold.
It should be noted that all the 12 mechanisms in Table II are representative CSMs—except for the TKED one. This means that Algorithms 1 and 3 are already capable of reproducing most known CSMs, while Algorithm 2 serves as a last resort for exhaustive enumeration. One could certainly apply Algorithm 2 to every SLM, but a more efficient approach is to filter them using experimentally observed ORs. As detailed in Ref. 27, the most commonly observed ORs in the B1–B2 transition are the Watanabe-Blaschko (WB) OR
[ 001 ] [ 110 ] B 1 ∥ [ 110 ] [ 001 ] B 2 , (101) [001][110]_{\mathrm{B1}} \parallel[110][001]_{\mathrm{B2}}, \tag*{(101)} [ 001 ] [ 110 ] B1 ∥ [ 110 ] [ 001 ] B2 , (101)
and the Okai-Fujiwara-Onodera (OFO) OR
[ 100 ] [ 111 ] B 1 ∥ [ 111 ] [ 100 ] B 2 . (102) [100][111]_{\mathrm{B1}} \parallel[111][100]_{\mathrm{B2}}. \tag*{(102)} [ 100 ] [ 111 ] B1 ∥ [ 111 ] [ 100 ] B2 . (102)
For both ORs, we computed the respective deviation angles φ 1 \varphi_1 φ 1 and φ 2 \varphi_2 φ 2 of each deformation gradient, defined as the minimal rotation required to produce the OR, as shown in Figure 9 (b)(Figure 9 c). We found that the deformation gradient of the WTM and TKED mechanisms is the only one that can produce the WB OR without rotation, which we denote by S W S_{\mathrm{W}} S W . On the other hand, the OFO OR can only be produced without rotation by two previously unreported deformation gradients, denoted as S 1 S_1 S 1 and S 2 S_2 S 2 . At this point, we can see that crystmatch provides a systematic way to infer the deformation gradient—and thus the SLM—based on experimental observations.
One naturally wonders whether, as μ max \mu_{\max} μ m a x increases, there exists a deformation gradient S S S with lower strain energy w w w than that of the TGS mechanism, or other S S S that can reproduce either OR without rotation. The answer to both questions is affirmative as long as we set μ max = 12 \mu_{\max} = 12 μ m a x = 12 , as shown in Figure 10 . Since the Buerger mechanism has d = 0 d = 0 d = 0 , we need not consider mechanisms with higher strain energy than it. Accordingly, we set w max = 13 × 10 8 w_{\max} = 13 \times10^8 w m a x = 13 × 1 0 8 J/m3 ^3 3 and performed a more comprehensive enumeration that took about 2 CPU hours, obtaining 9987 noncongruent SLMs and 5432 distinct deformation gradients. Despite the total numbers increasing by more than an order of magnitude, only a handful of new cases emerged with w w w lower than that of the TGS mechanism, φ 1 = 0 \varphi_1 = 0 φ 1 = 0 , or φ 2 = 0 \varphi_2 = 0 φ 2 = 0 .
Figure 10. All deformation gradients S S S with μ 0 ≤ 12 \mu_0 \le12 μ 0 ≤ 12 and w ≤ 13 × 10 8 w \le13 \times10^8 w ≤ 13 × 1 0 8 J/m3 ^3 3 . Only the Buerger mechanism is omitted, as it has already been shown in Figure 9 . (a) Each S S S is colored according to μ 0 \mu_0 μ 0 , the minimal multiplicity required for an SLM to have S S S . There are several S S S with w w w less than the TGS mechanism, but also higher d 0 d_0 d 0 and μ 0 \mu_0 μ 0 . (b)(c) Each S S S is colored according to the deviation angles. Blue crosses highlight those S S S with φ 1 = 0 \varphi_1 = 0 φ 1 = 0 or φ 2 = 0 \varphi_2 = 0 φ 2 = 0 .
Exhaustive enumeration
Now we assign shuffle-distance weights to Cs and Cl atoms. If equal weights are used, a large number of CSMs will exhibit identical d d d values, as shown in Figure 11 . A physically reasonable approach is to consider the initial velocity v v v required to move from the initial state to the transition state on the PES within an average free time, which is proportional to the unweighted d d d . Statistical mechanics tells us that heavier atoms are less likely to acquire velocities, since kinetic energy T i = 1 2 m i v i 2 T_i = \frac{1}{2}m_i v_i^2 T i = 2 1 m i v i 2 . Therefore, each atom’s contribution to d 2 d^2 d 2 should be weighted as θ i ∝ m i \theta_i \propto m_i θ i ∝ m i , and ℓ = 2 \ell= 2 ℓ = 2 is thus an appropriate choice. This leads to ln ( θ C s / θ C l ) ≈ 1.32 \ln(\theta_{\mathrm{Cs}}/\theta_{\mathrm{Cl}}) \approx1.32 ln ( θ Cs / θ Cl ) ≈ 1.32 , which is sufficient to lift the degeneracy in d d d .
Figure 11. How the shuffle distance d d d depends on the weighting scheme, i.e., the ratio θ C s / θ C l \theta_{\mathrm{Cs}}/\theta_{\mathrm{Cl}} θ Cs / θ Cl for SDBPs in CsCl. The figure shows 51 CSMs with the same SLM (μ = 6 \mu= 6 μ = 6 ), whose d d d has only 8 distinct values when θ C s = θ C l \theta_{\mathrm{Cs}} = \theta_{\mathrm{Cl}} θ Cs = θ Cl . Colors are used to distinguish between different CSMs.
To investigate the distribution of nonrepresentative CSMs and to reproduce the TKED mechanism, Algorithm 2 is applied to each SLM with μ ≤ 6 \mu\le6 μ ≤ 6 and w ≤ 13 × 10 8 J / m 3 w \le13 \times10^{8}\,\mathrm{J}/\mathrm{m}^{3} w ≤ 13 × 1 0 8 J / m 3 , using d max = 1.8 A ˚ d_{\max}=1.8\,\text{\AA} d m a x = 1.8 A ˚ . This took about 3 hours, producing 320 757 CSMs, as shown in Figure 12 . However, if one is only interested in the CSMs that exactly conform to the WB OR, it is sufficient to apply Algorithm 2 only to those SLMs with S W S_W S W , taking merely 7 min 39 s. Figure 13 shows all CSMs with S W S_W S W , from which one can see that while S W S_W S W belongs to the SLM of the WTM mechanism (μ = 2 \mu=2 μ = 2 ), it also belongs to 7 noncongruent SLMs with μ = 4 \mu=4 μ = 4 and 13 noncongruent SLMs with μ = 6 \mu=6 μ = 6 . This is because for a given ( H A , H B , Q ) ∈ IMT ( μ ) (H_A,H_B,Q)\in\operatorname{IMT}(\mu) ( H A , H B , Q ) ∈ IMT ( μ ) , any M ∈ Z 3 × 3 M\in\mathbb{Z}^{3\times3} M ∈ Z 3 × 3 with det M > 0 \det M>0 det M > 0 induces an ( H A ′ , H B ′ , Q ′ ) ∈ IMT ( μ det M ) (H'_A,H'_B,Q')\in\operatorname{IMT}(\mu\det M) ( H A ′ , H B ′ , Q ′ ) ∈ IMT ( μ det M ) with the same deformation gradient, where
Figure 12. All CSMs with μ ≤ 6 \mu\le6 μ ≤ 6 , w ≤ 13 × 10 8 J / m 3 w \le13 \times10^{8}\,\mathrm{J}/\mathrm{m}^{3} w ≤ 13 × 1 0 8 J / m 3 , and d ≤ 1.8 A ˚ d \le1.8\,\text{\AA} d ≤ 1.8 A ˚ . Only the Buerger CSM is omitted, as it has already been shown in Fig. 9. Diamonds and crosses indicate representative and nonrepresentative CSMs, respectively. Each CSM is colored according to its multiplicity.
Figure 13. All CSMs with μ ≤ 6 \mu\le6 μ ≤ 6 and deformation gradient S W S_W S W . CSMs that can be produced by Algorithm 2 using the same SLM are drawn in the same horizontal coordinate. Yellow, green, and indigo represent μ = 2 \mu=2 μ = 2 , 4, 6, respectively. Gray lines point out the CSMs of the WTM and TKED mechanisms. Note that CSMs with μ = 2 \mu=2 μ = 2 also acquire PCT representations in SLMs with μ = 4 , 6 \mu=4,6 μ = 4 , 6 .
H A ′ = hnf ( H A M ) , H'_A=\operatorname{hnf}(H_A M), H A ′ = hnf ( H A M ) ,
H B ′ = hnf ( H B Q M ) , H'_B=\operatorname{hnf}(H_B Q M), H B ′ = hnf ( H B QM ) ,
Q ′ = H B ′ − 1 H B Q H A − 1 H A ′ . Q'=H_B'^{-1}H_B Q H_A^{-1}H'_A. Q ′ = H B ′ − 1 H B Q H A − 1 H A ′ .
Overall, the total number of CSMs increases rapidly with both μ \mu μ and d max d_{\max} d m a x .
Note that J p , t 1 , … , t Z ~ J_{p,t_1,\ldots,t_{\widetilde{Z}}} J p , t 1 , … , t Z satisfying Eq. (57) may have a period smaller than Z ~ \widetilde{Z} Z . Consequently, the WTM CSM J W J_W J W is reproduced in every PCT ⋆ ( L ~ A , L ~ B , S W ) \operatorname{PCT}^{\star}(\widetilde{L}_A,\widetilde{L}_B,S_W) PCT ⋆ ( L A , L B , S W ) such that L ~ B \widetilde{L}_B L B is a sublattice of the shuffle lattice of J W ∘ S W − 1 J_W\circ S_W^{-1} J W ∘ S W − 1 ; see Figure 13 . In fact, all CSMs exhibit this repetitive property under the PCT representation. Although one could easily eliminate it by modifying Algorithm 2 and Definition 17, doing so is unnecessary, since the current formalism ensures that PCT ( L ~ A , L ~ B , S ) \operatorname{PCT}(\widetilde{L}_A,\widetilde{L}_B,S) PCT ( L A , L B , S ) precisely consists of all possible CSM that a molecular-dynamics simulation employing periodic boundary conditions L ~ A \widetilde{L}_A L A (initial) and L ~ B \widetilde{L}_B L B (final), undergoing the deformation S S S , may produce—even when the resulting CSM possesses a smaller intrinsic period.
Effect of pressure on lattice mismatch
The densities of two solid phases of the same material can differ significantly, making their lattice mismatch and strain energy inevitably large. In such cases, pressure plays a decisive role in the occurrence of SSPTs. For example, at 1500 K, the graphite-diamond coexistence pressure estimated by the Berman-Simon line is ∼ 5 G P a \sim5\,\mathrm{GPa} ∼ 5 GPa , while the SSPT is not observed until ∼ 12 G P a \sim12\,\mathrm{GPa} ∼ 12 GPa [51 , 52 ] . Previous studies also suggest that when the pressure is further increased to 20–50 GPa, both the critical nucleus size and nucleation energy decrease, as shown in Figure 2 of Ref. 10. However, lattice mismatch cannot be quantified unless how lattices match is self-evident, or defined in advance—this is precisely what the concept of SLM provides. By enumerating all possible deformation gradients, Algorithm 1 enables a comprehensive analysis of lattice mismatch.
We investigated the graphite-to-diamond transition under pressures P = 0 , 10 , 20 , 30 , 40 , 50 P = 0, 10, 20, 30, 40, 50 P = 0 , 10 , 20 , 30 , 40 , 50 GPa. The enumeration range was specified as μ max = 6 \mu_{\max} = 6 μ m a x = 6 (i.e., Z ~ ≤ 24 \widetilde{Z} \le24 Z ≤ 24 ) and w max = 5 × 10 10 w_{\max} = 5 \times10^{10} w m a x = 5 × 1 0 10 J/m3 ^3 3 to ensure inclusion of all established mechanisms, with the initial and final structures as well as elastic tensors calculated at each P P P . The minimal multiplicity μ 0 \mu_0 μ 0 and minimal shuffle distance d 0 d_0 d 0 for each deformation gradient is also computed as we did in Section V A. For the case of P = 0 P = 0 P = 0 , enumerating the SLMs and computing d 0 d_0 d 0 took 9 min 29 s and 37 s, respectively. The joint distribution of w w w and d 0 d_0 d 0 , as well as the spectrum of w w w are shown in Figure 14 . We can see that as pressure increases, the strain energy of those deformation gradients with small d 0 d_0 d 0 or small w w w decreases significantly. However, some other deformation gradients—particularly those with larger μ 0 \mu_0 μ 0 and d 0 d_0 d 0 —exhibit opposite or even nonmonotonic trends. This suggests that the actual SSPT mechanism may vary under different pressures. Overall, the “lattice mismatch spectrum” in Figure 14 (b) extends leftward with increasing pressure, consistent with previous experimental and computational studies.
Figure 14. All deformation gradients S S S with μ 0 ≤ 6 \mu_0 \le6 μ 0 ≤ 6 and w ≤ 500 × 10 8 w \le500 \times10^8 w ≤ 500 × 1 0 8 J/m3 ^3 3 . Colors are used to distinguish between different multiplicities. (a) The distribution of w ( S ) w(S) w ( S ) and d 0 ( S ) d_0(S) d 0 ( S ) at each pressure P P P . Solid lines connect points representing the same SLM under different P P P , whose marker shapes change with increasing pressure, as indicated in the legend at the lower left. (b) The lattice mismatch spectrum at each P P P . Solid lines show the diverse behaviors of w w w as a function of P P P for different SLMs.
Summary
We have introduced a cell-independent formalism that unequivocally defines the deformation gradient, SLM, and standard shuffle of a CSM, as well as the symmetry-induced congruence relations on CSM(A , B \mathcal{A}, \mathcal{B} A , B ) and SLM(A , B \mathcal{A}, \mathcal{B} A , B ). This maps all possible CSMs of an SSPT onto a tree structure, which is finite up to congruence classes as long as the multiplicity, strain energy and shuffle distance are bounded. Using the IMT and PCT representation, each CSM is encoded in a tuple of integer matrices with minimal redundancy. Based on this, Algorithms 1–3 have been proposed for the exhaustive enumeration of CSMs and SLMs, unveiling novel SSPT mechanisms with unprecedentedly low strain or desired ORs. They lay the groundwork for predicting CSM energy barriers via machine learning and can be seamlessly integrated with widely used methods with negligible computational cost. One may also use them to study defect migration or heteroepitaxy [24 , 53 , 54 ] . All algorithms are implemented in the command-line tool CRYSTMATCH, which is open-sourced and freely available to the community [49 ] .
Acknowledgments
We acknowledge helpful discussions with Xu-Yuan Zhou, Yuze Sun, Wei-Jian Jiang, Yi-Chi Zhang, Jia-Xi Zeng, Qi Liu, Yi Yang, Qing-Yang Zheng, and Jia-Cheng Gao. We are supported by the National Science Foundation of China under Grants No. 123B2048, No. 12204015, No. 12234001, No. 12404257, No. 12474215, and No. 62321004, and the National Basic Research Program of China under Grants No. 2021YFA1400500 and No. 2022YFA1403500. The computational resources were provided by the supercomputer center at Peking University, China.
Lemmas and proofs
Proof of Lemma 1. t ∈ R 3 \mathbf{t} \in\mathbb{R}^{3} t ∈ R 3 is a translation element of J \mathcal{J} J if and only if (9) holds, which is equivalent to:
A + t A ← + t A A → J B → + t B B + t B + t ↓ + t ↓ + t ↓ + t ↓ A + t A ← + t A A → J B → + t B B + t B (103) \begin{CD}
\mathcal{A}+\mathbf{t}_{A} @< {+\mathbf{t}_{A}} << \mathcal{A} @>{\mathcal{J}}>> \mathcal{B} @>{+\mathbf{t}_{B}}>> \mathcal{B}+\mathbf{t}_{B}\\
@V {+\mathbf{t}} VV @V {+\mathbf{t}} VV @V {+\mathbf{t}} VV @V {+\mathbf{t}} VV\\
\mathcal{A}+\mathbf{t}_{A} @< {+\mathbf{t}_{A}} << \mathcal{A} @>{\mathcal{J}}>> \mathcal{B} @>{+\mathbf{t}_{B}}>> \mathcal{B}+\mathbf{t}_{B} \tag*{(103)}
\end{CD} A + t A + t ↓ ⏐ A + t A + t A + t A A + t ↓ ⏐ A J J B + t ↓ ⏐ B + t B + t B B + t B + t ↓ ⏐ B + t B (103)
The outer loop of the above diagram means that t \mathbf{t} t is a translation element of ( + t B ) ∘ J ∘ ( − t A ) (+\mathbf{t}_{B}) \circ\mathcal{J} \circ(-\mathbf{t}_{A}) ( + t B ) ∘ J ∘ ( − t A ) . The above derivation is reversible, so that the two CSMs have the same translation elements. ■
Proof of Lemma 2. We prove the following proposition for each positive integer n n n by induction: If L L L is an addition group on R n \mathbb{R}^{n} R n with rank n n n and
λ ( L ) = inf t ∈ L ∖ { 0 } ∣ t ∣ > 0 , (104) \lambda(L)=\inf_{\mathbf{t}\in L\setminus\{0\}}|\mathbf{t}|>0, \tag*{(104)} λ ( L ) = t ∈ L ∖ { 0 } inf ∣ t ∣ > 0 , (104)
then
∃ t 1 , … , t n , L = { ∑ i = 1 n k i t i ∣ k 1 , … , k n ∈ Z } . (105) \exists\mathbf{t}_{1},\ldots,\mathbf{t}_{n},\quad L=\left\{\left.\sum_{i=1}^{n}k_{i}\mathbf{t}_{i}\right|k_{1},\ldots,k_{n}\in\mathbb{Z}\right\}. \tag*{(105)} ∃ t 1 , … , t n , L = { i = 1 ∑ n k i t i k 1 , … , k n ∈ Z } . (105)
Since (104) implies (4) , Lemma 2 is nothing but a special case of this proposition for n = 3 n=3 n = 3 .
Base case. For n = 1 n=1 n = 1 , let t 1 \mathbf{t}_{1} t 1 denote an element of L L L with length λ ( L ) \lambda(L) λ ( L ) . Such an element must exist; otherwise, L L L would have infinitely many elements with bounded lengths, and hence a cluster point (by the Bolzano-Weierstrass theorem), which contradicts (4) . Since L L L is an addition group, we have { k 1 t 1 ∣ k 1 ∈ Z } ⊂ L \{k_{1}\mathbf{t}_{1}\mid k_{1}\in\mathbb{Z}\}\subset L { k 1 t 1 ∣ k 1 ∈ Z } ⊂ L . There are no other elements in L L L ; otherwise, the minimum distance between elements in L L L would be smaller than λ ( L ) \lambda(L) λ ( L ) .
Induction step. Now we show that for every m ≥ 1 m\ge1 m ≥ 1 , if (105) holds for n = m n=m n = m , it also holds for n = m + 1 n=m+1 n = m + 1 . Let t 1 \mathbf{t}_{1} t 1 denote an element of L ⊂ R m + 1 L\subset\mathbb{R}^{m+1} L ⊂ R m + 1 with length λ ( L ) \lambda(L) λ ( L ) . Any element in R m + 1 \mathbb{R}^{m+1} R m + 1 can be uniquely decomposed as
v = c 1 t 1 + v ′ , (106) \mathbf{v}=c_{1}\mathbf{t}_{1}+\mathbf{v}^{\prime}, \tag*{(106)} v = c 1 t 1 + v ′ , (106)
where c 1 ∈ R c_{1}\in\mathbb{R} c 1 ∈ R and v ′ ∈ span R { t 1 } ⊥ \mathbf{v}^{\prime}\in\operatorname{span}_{\mathbb{R}}\{\mathbf{t}_{1}\}^{\perp} v ′ ∈ span R { t 1 } ⊥ is orthogonal to t 1 \mathbf{t}_{1} t 1 . This defines a projection mapping
π : R m + 1 → span R { t 1 } ⊥ , (107) \pi:\mathbb{R}^{m+1}\to\operatorname{span}_{\mathbb{R}}\{\mathbf{t}_{1}\}^{\perp}, \tag*{(107)} π : R m + 1 → span R { t 1 } ⊥ , (107)
v ↦ v ′ . (108) \mathbf{v}\mapsto\mathbf{v}^{\prime}. \tag*{(108)} v ↦ v ′ . (108)
Since π \pi π is a linear mapping, the image of L L L under this mapping, π ( L ) \pi(L) π ( L ) , is an additive group with rank m m m . In fact, we also have λ ( π ( L ) ) > 0 \lambda(\pi(L))>0 λ ( π ( L )) > 0 ; otherwise, L L L would have infinitely many elements with bounded lengths, and hence a cluster point. Therefore, π ( L ) \pi(L) π ( L ) satisfies the proposition for n = m n=m n = m , so there must exist t 2 , … , t m + 1 ∈ L \mathbf{t}_{2},\ldots,\mathbf{t}_{m+1}\in L t 2 , … , t m + 1 ∈ L whose images under π \pi π generate
π ( L ) = { ∑ i = 2 m + 1 k i π ( t i ) ∣ k 2 , … , k m + 1 ∈ Z } . (109) \pi(L)=\left\{\left.\sum_{i=2}^{m+1}k_{i}\pi(\mathbf{t}_{i})\right|k_{2},\ldots,k_{m+1}\in\mathbb{Z}\right\}. \tag*{(109)} π ( L ) = { i = 2 ∑ m + 1 k i π ( t i ) k 2 , … , k m + 1 ∈ Z } . (109)
Also, since L L L is an addition group, we have
{ ∑ i = 1 m + 1 k i t i ∣ k 1 , … , k m + 1 ∈ Z } ⊂ L , (110) \left\{\left.\sum_{i=1}^{m+1}k_{i}\mathbf{t}_{i}\right|k_{1},\ldots,k_{m+1}\in\mathbb{Z}\right\}\subset L, \tag*{(110)} { i = 1 ∑ m + 1 k i t i k 1 , … , k m + 1 ∈ Z } ⊂ L , (110)
and we only need to show that there are no other elements in L L L . Note that any t ∈ L \mathbf{t}\in L t ∈ L can be expressed as
t = c 1 t 1 + ∑ i = 2 m + 1 c i t i , (111) \mathbf{t}=c_{1}\mathbf{t}_{1}+\sum_{i=2}^{m+1}c_{i}\mathbf{t}_{i}, \tag*{(111)} t = c 1 t 1 + i = 2 ∑ m + 1 c i t i , (111)
for some c 1 , … , c m + 1 ∈ R c_{1},\ldots,c_{m+1}\in\mathbb{R} c 1 , … , c m + 1 ∈ R . Applying π \pi π to (111) and use (109) , we can see that c 2 , … , c m + 1 c_{2},\ldots,c_{m+1} c 2 , … , c m + 1 must be integers. This implies that
( c 1 − ⌊ c 1 ⌋ ) t 1 ∈ L , (112) \left(c_{1}-\lfloor c_{1}\rfloor\right)\mathbf{t}_{1}\in L, \tag*{(112)} ( c 1 − ⌊ c 1 ⌋ ) t 1 ∈ L , (112)
where ⌊ c 1 ⌋ \lfloor c_{1}\rfloor ⌊ c 1 ⌋ denotes the greatest integer less than or equal to c 1 c_{1} c 1 . If c 1 ∉ Z c_{1}\notin\mathbb{Z} c 1 ∈ / Z , the length of (112) would be nonzero and smaller than λ ( L ) \lambda(L) λ ( L ) , which contradicts (104) . At this point, we can see that all coefficients in (111) are integers, so that the proposition holds for n = m + 1 n=m+1 n = m + 1 . ■
Proof of Lemma 3. If C ~ = C M \widetilde{C}=CM C = C M for some M ∈ Z 3 × 3 M\in\mathbb{Z}^{3\times3} M ∈ Z 3 × 3 , then C ~ ( Z 3 ) = C ( M ( Z 3 ) ) \widetilde{C}(\mathbb{Z}^{3})=C(M(\mathbb{Z}^{3})) C ( Z 3 ) = C ( M ( Z 3 )) is a sublattice of C ( Z 3 ) C(\mathbb{Z}^{3}) C ( Z 3 ) since M ( Z 3 ) M(\mathbb{Z}^{3}) M ( Z 3 ) is a sublattice of Z 3 \mathbb{Z}^{3} Z 3 . Conversely, if C ~ ( Z 3 ) \widetilde{C}(\mathbb{Z}^{3}) C ( Z 3 ) is a sublattice of C ( Z 3 ) C(\mathbb{Z}^{3}) C ( Z 3 ) , there exist k 1 , k 2 , k 3 ∈ Z 3 \mathbf{k}_{1},\mathbf{k}_{2},\mathbf{k}_{3}\in\mathbb{Z}^{3} k 1 , k 2 , k 3 ∈ Z 3 such that the i i i -th column of C ~ \widetilde{C} C equals C k i C\mathbf{k}_{i} C k i , i.e., C ~ = C [ k 1 , k 2 , k 3 ] \widetilde{C}=C[\mathbf{k}_{1},\mathbf{k}_{2},\mathbf{k}_{3}] C = C [ k 1 , k 2 , k 3 ] . To see that the index of the sublattice is the determinant ∣ det M ∣ |\det M| ∣ det M ∣ , we only need to use the elementary divisor theorem [55 ] , which states that the quotient group C ( Z 3 ) / C ~ ( Z 3 ) C(\mathbb{Z}^{3})/\widetilde{C}(\mathbb{Z}^{3}) C ( Z 3 ) / C ( Z 3 ) is isomorphic to a Z \mathbb{Z} Z -module of size ∣ det M ∣ |\det M| ∣ det M ∣ . ■
Proof of Lemma 4. Arbitrarily take a 1 , … , a Z A ∈ A \mathbf{a}_{1},\ldots,\mathbf{a}_{Z_{A}}\in\mathcal{A} a 1 , … , a Z A ∈ A that are L A L_{A} L A -inequivalent, and t 1 , … , t k ∈ L A \mathbf{t}_{1},\ldots,\mathbf{t}_{k}\in L_{A} t 1 , … , t k ∈ L A that are L ~ A \widetilde{L}_{A} L A -inequivalent. We have
A = ⨆ i = 1 Z A ( a i + L A ) (113) \mathcal{A}=\bigsqcup_{i=1}^{Z_{A}}(\mathbf{a}_{i}+L_{A}) \tag*{(113)} A = i = 1 ⨆ Z A ( a i + L A ) (113)
= ⨆ i = 1 Z A ( a i + ⨆ j = 1 k ( t j + L ~ A ) ) (114) =\bigsqcup_{i=1}^{Z_{A}}\left(\mathbf{a}_{i}+\bigsqcup_{j=1}^{k}(\mathbf{t}_{j}+\widetilde{L}_{A})\right) \tag*{(114)} = i = 1 ⨆ Z A ( a i + j = 1 ⨆ k ( t j + L A ) ) (114)
= ⨆ i = 1 Z A ⨆ j = 1 k ( ( a i + t j ) + L ~ A ) , (115) =\bigsqcup_{i=1}^{Z_{A}}\bigsqcup_{j=1}^{k}\left((\mathbf{a}_{i}+\mathbf{t}_{j})+\widetilde{L}_{A}\right), \tag*{(115)} = i = 1 ⨆ Z A j = 1 ⨆ k ( ( a i + t j ) + L A ) , (115)
where ⨆ \bigsqcup ⨆ denotes the disjoint union of sets. Since each ( a i + t j ) + L ~ A (\mathbf{a}_{i}+\mathbf{t}_{j})+\widetilde{L}_{A} ( a i + t j ) + L A is a distinct L ~ A \widetilde{L}_{A} L A -equivalence class, we have ∣ A / A ~ ∣ = k Z A |\mathcal{A}/\widetilde{\mathcal{A}}|=kZ_{A} ∣ A / A ∣ = k Z A . ■
Proof of Lemma 5. Note that
C ( Z 3 ) = C ′ ( Z 3 ) ⟺ C − 1 C ′ ( Z 3 ) = Z 3 (116) C(\mathbb{Z}^{3})=C^{\prime}(\mathbb{Z}^{3})\quad\Longleftrightarrow\quad C^{-1}C^{\prime}(\mathbb{Z}^{3})=\mathbb{Z}^{3} \tag*{(116)} C ( Z 3 ) = C ′ ( Z 3 ) ⟺ C − 1 C ′ ( Z 3 ) = Z 3 (116)
⟺ C − 1 C ′ ∈ GL ( 3 , Z ) , (117) \Longleftrightarrow\quad C^{-1}C^{\prime}\in\operatorname{GL}(3,\mathbb{Z}), \tag*{(117)} ⟺ C − 1 C ′ ∈ GL ( 3 , Z ) , (117)
where we have used (40) . ■
Proof of Lemma 6. The existence of H H H and Q Q Q as well as the uniqueness of H H H are proved in Ref. 55. To see that Q Q Q is also unique, note that Q = H − 1 M Q=H^{-1}M Q = H − 1 M . ■
Proof of Lemma 7. S T S S^{T}S S T S is positive-definite, so it has three orthogonal eigenvectors v 1 , v 2 , v 3 \mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3} v 1 , v 2 , v 3 (arranged in right-handed order) with eigenvalues λ 1 ≥ λ 2 ≥ λ 3 > 0 \lambda_{1}\geq\lambda_{2}\geq\lambda_{3}>0 λ 1 ≥ λ 2 ≥ λ 3 > 0 . Let s i = λ i s_{i}=\sqrt{\lambda_{i}} s i = λ i , V = [ v 1 , v 2 , v 3 ] ∈ SO ( 3 ) V=[\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3}]\in\operatorname{SO}(3) V = [ v 1 , v 2 , v 3 ] ∈ SO ( 3 ) , and U = S V Σ − 1 U=SV\Sigma^{-1} U = S V Σ − 1 . We have U ∈ SO ( 3 ) U\in\operatorname{SO}(3) U ∈ SO ( 3 ) since U T U = I U^{T}U=I U T U = I and det U = 1 \det U=1 det U = 1 . Since λ i \lambda_{i} λ i is uniquely determined by S S S , so is s i s_{i} s i . ■
Lemma 8. When ℓ = 2 \ell=2 ℓ = 2 , the right-hand side of Eq. (68) attains the minimum if and only if τ = a ~ i − J ~ ( a ~ i ) \boldsymbol{\tau}=\tilde{\mathbf{a}}_{i}-\tilde{\mathcal{J}}(\tilde{\mathbf{a}}_{i}) τ = a ~ i − J ~ ( a ~ i ) , where the overline denotes the mean value
v ‾ i = ∑ i = 1 Z ~ θ i v i . (118) \overline{\mathbf{v}}_{i}=\sum_{i=1}^{\widetilde{Z}}\theta_{i}\mathbf{v}_{i}. \tag*{(118)} v i = i = 1 ∑ Z θ i v i . (118) Consequently, a CSM with PCT ( p , t 1 , ⋯ , t Z ~ ) (p,t_{1},\cdots,t_{\widetilde{Z}}) ( p , t 1 , ⋯ , t Z ) has
d ( J p , t 1 , … , t Z ~ ) = ∣ b ~ p ( i ) + t ~ i − a ~ i − b ~ j − t ~ j + a ~ j ∣ 2 , (119) d(\mathcal{J}_{p,t_{1},\ldots,t_{\widetilde{Z}}})=\sqrt{\left\lvert\tilde{\mathbf{b}}_{p(i)}+\tilde{\mathbf{t}}_{i}-\tilde{\mathbf{a}}_{i}-\tilde{\mathbf{b}}_{j}-\tilde{\mathbf{t}}_{j}+\tilde{\mathbf{a}}_{j}\right\rvert^{2}}, \tag*{(119)} d ( J p , t 1 , … , t Z ) = b ~ p ( i ) + t ~ i − a ~ i − b ~ j − t ~ j + a ~ j 2 , (119) where b ~ i = V Σ − 1 / 2 U T b i \tilde{\mathbf{b}}_{i}=V\Sigma^{-1/2}U^{T}\mathbf{b}_{i} b ~ i = V Σ − 1/2 U T b i is deformed from the L B L_{B} L B -motif that defines the PCT, and so is t ~ i = V Σ − 1 / 2 U T t i \tilde{\mathbf{t}}_{i}=V\Sigma^{-1/2}U^{T}\mathbf{t}_{i} t ~ i = V Σ − 1/2 U T t i .
Proof. For any v 1 , … , v Z ~ ∈ R 3 \mathbf{v}_{1},\ldots,\mathbf{v}_{\widetilde{Z}}\in\mathbb{R}^{3} v 1 , … , v Z ∈ R 3 and τ ∈ R 3 \boldsymbol{\tau}\in\mathbb{R}^{3} τ ∈ R 3 , we have
∣ v i + τ ∣ 2 (120) \left\lvert\mathbf{v}_{i}+\boldsymbol{\tau}\right\rvert^{2} \tag*{(120)} ∣ v i + τ ∣ 2 (120) = ∣ ( v i − v j ) + ( τ + v j ) ∣ 2 (121) =\left\lvert(\mathbf{v}_{i}-\mathbf{v}_{j})+(\boldsymbol{\tau}+\mathbf{v}_{j})\right\rvert^{2} \tag*{(121)} = ∣ ( v i − v j ) + ( τ + v j ) ∣ 2 (121) = ∣ v i − v j ∣ 2 + 2 ( v i − v j ) ⋅ ( τ + v j ) + ∣ τ + v j ∣ 2 (122) =\left\lvert\mathbf{v}_{i}-\mathbf{v}_{j}\right\rvert^{2}+2(\mathbf{v}_{i}-\mathbf{v}_{j})\cdot(\boldsymbol{\tau}+\mathbf{v}_{j})+\left\lvert\boldsymbol{\tau}+\mathbf{v}_{j}\right\rvert^{2} \tag*{(122)} = ∣ v i − v j ∣ 2 + 2 ( v i − v j ) ⋅ ( τ + v j ) + ∣ τ + v j ∣ 2 (122) = ∣ v i − v j ∣ 2 + 2 ( v i − v j ) ⋅ ( τ + v j ) + ∣ τ + v j ∣ 2 (123) =\left\lvert\mathbf{v}_{i}-\mathbf{v}_{j}\right\rvert^{2}+2(\mathbf{v}_{i}-\mathbf{v}_{j})\cdot(\boldsymbol{\tau}+\mathbf{v}_{j})+\left\lvert\boldsymbol{\tau}+\mathbf{v}_{j}\right\rvert^{2} \tag*{(123)} = ∣ v i − v j ∣ 2 + 2 ( v i − v j ) ⋅ ( τ + v j ) + ∣ τ + v j ∣ 2 (123) = ∣ v i − v j ∣ 2 + ∣ τ + v j ∣ 2 . (124) =\left\lvert\mathbf{v}_{i}-\mathbf{v}_{j}\right\rvert^{2}+\left\lvert\boldsymbol{\tau}+\mathbf{v}_{j}\right\rvert^{2}. \tag*{(124)} = ∣ v i − v j ∣ 2 + ∣ τ + v j ∣ 2 . (124) We can see that ∣ v i + τ ∣ 2 \left\lvert\mathbf{v}_{i}+\boldsymbol{\tau}\right\rvert^{2} ∣ v i + τ ∣ 2 attains its minimum ∣ v i − v j ∣ 2 \left\lvert\mathbf{v}_{i}-\mathbf{v}_{j}\right\rvert^{2} ∣ v i − v j ∣ 2 if and only if τ = − v i \boldsymbol{\tau}=-\mathbf{v}_{i} τ = − v i . Hence, when ℓ = 2 \ell=2 ℓ = 2 , we have
d ( J ) = ∣ J ~ ( a ~ i ) − a ~ i − J ~ ( a ~ j ) + a ~ j ∣ 2 , (125) d(\mathcal{J})=\sqrt{\left\lvert\tilde{\mathcal{J}}(\tilde{\mathbf{a}}_{i})-\tilde{\mathbf{a}}_{i}-\tilde{\mathcal{J}}(\tilde{\mathbf{a}}_{j})+\tilde{\mathbf{a}}_{j}\right\rvert^{2}}, \tag*{(125)} d ( J ) = J ~ ( a ~ i ) − a ~ i − J ~ ( a ~ j ) + a ~ j 2 , (125) which is identical to Eq. (119) . ■
Lemma 9. Let A \mathcal{A} A be a crystal structure and L L L a sublattice of A \mathcal{A} A . If we additionally require that A ⊂ R 3 \mathcal{A}\subset\mathbb{R}^{3} A ⊂ R 3 has no cluster points, then ∣ A / L ∣ \lvert\mathcal{A}/L\rvert ∣ A / L ∣ is finite.
Proof. We assume by contradiction that the quotient set A / L \mathcal{A}/L A / L is infinite. Take t 1 , t 2 , t 3 ∈ L \mathbf{t}_{1},\mathbf{t}_{2},\mathbf{t}_{3}\in L t 1 , t 2 , t 3 ∈ L that satisfy Eq. (105) and consider the parallelepiped
P=\left\{\sum_{i=1}^{3}x_{i}\mathbf{t}_{i}\mathrel{\left|}x_{1},x_{2},x_{3}\in[0,1)\right.\right\}. \tag*{(126)}
Any element in R 3 \mathbb{R}^{3} R 3 can be uniquely decomposed as
v = ∑ i = 1 3 c i t i , (127) \mathbf{v}=\sum_{i=1}^{3}c_{i}\mathbf{t}_{i}, \tag*{(127)} v = i = 1 ∑ 3 c i t i , (127)
where c 1 , c 2 , c 3 ∈ R c_{1},c_{2},c_{3}\in\mathbb{R} c 1 , c 2 , c 3 ∈ R . Therefore, the mapping
π : R 3 → P , (128) \pi:\mathbb{R}^{3}\to P, \tag*{(128)} π : R 3 → P , (128)
∑ i = 1 3 c i t i ↦ ∑ i = 1 3 ( c i − ⌊ c i ⌋ ) t i , (129) \sum_{i=1}^{3}c_{i}\mathbf{t}_{i}\mapsto\sum_{i=1}^{3}(c_{i}-\lfloor c_{i}\rfloor)\mathbf{t}_{i}, \tag*{(129)} i = 1 ∑ 3 c i t i ↦ i = 1 ∑ 3 ( c i − ⌊ c i ⌋) t i , (129)
is well-defined. Note that the image of each a + L ∈ A / L \mathbf{a}+L\in\mathcal{A}/L a + L ∈ A / L under π \pi π is a single element in P ∩ A P\cap\mathcal{A} P ∩ A , and
π ( a 1 + L ) = π ( a 2 + L ) ⟹ a 1 + L = a 2 + L , (130) \pi(\mathbf{a}_{1}+L)=\pi(\mathbf{a}_{2}+L)\quad\Longrightarrow\quad\mathbf{a}_{1}+L=\mathbf{a}_{2}+L, \tag*{(130)} π ( a 1 + L ) = π ( a 2 + L ) ⟹ a 1 + L = a 2 + L , (130)
i.e., π : A / L → P ∩ A \pi:\mathcal{A}/L\to P\cap\mathcal{A} π : A / L → P ∩ A is injective. Since A / L \mathcal{A}/L A / L is infinite, its image π ( A / L ) \pi(\mathcal{A}/L) π ( A / L ) is also infinite, and so is P ∩ A P\cap\mathcal{A} P ∩ A . The Bolzano-Weierstrass theorem then states that P ∩ A P\cap\mathcal{A} P ∩ A must have a cluster point. ■
:::
Lemma 10. Let L L L be a lattice, and L 1 , L 2 L_{1},L_{2} L 1 , L 2 its sublattice. The intersection set L 1 ∩ L 2 L_{1}\cap L_{2} L 1 ∩ L 2 is full rank.
Proof. Let C , C 1 , C 2 C,C_{1},C_{2} C , C 1 , C 2 be base matrices of L , L 1 , L 2 L,L_{1},L_{2} L , L 1 , L 2 , respectively. We only need to prove that there exist nonsingular N 1 , N 2 ∈ Z 3 × 3 N_{1},N_{2}\in\mathbb{Z}^{3\times3} N 1 , N 2 ∈ Z 3 × 3 such that
C 1 N 1 = C 2 N 2 . (131) C_{1}N_{1}=C_{2}N_{2}. \tag*{(131)} C 1 N 1 = C 2 N 2 . (131) Lemma 3 states that C 1 = C M 1 C_{1}=CM_{1} C 1 = C M 1 and C 2 = C M 2 C_{2}=CM_{2} C 2 = C M 2 for some nonsingular M 1 , M 2 ∈ Z 3 × 3 M_{1},M_{2}\in\mathbb{Z}^{3\times3} M 1 , M 2 ∈ Z 3 × 3 . Therefore, Eq. (131) is equivalent to
N 1 = M 1 − 1 M 2 N 2 . (132) N_{1}=M_{1}^{-1}M_{2}N_{2}. \tag*{(132)} N 1 = M 1 − 1 M 2 N 2 . (132) Since M 1 − 1 M 2 M_{1}^{-1}M_{2} M 1 − 1 M 2 is rational, we can always let m m m be a common multiple of the denominators of its elements. Then we have nonsingular N 1 = m M 1 − 1 M 2 N_{1}=mM_{1}^{-1}M_{2} N 1 = m M 1 − 1 M 2 and N 2 = m I N_{2}=mI N 2 = m I that satisfies Eq. (132) . ■
Details of Algorithm 1
For empirical reasons, we generate S 0 ∈ Ω S 0 S_{0}\in\Omega_{S_{0}} S 0 ∈ Ω S 0 using the SVD S 0 = U Σ V T S_{0}=U\Sigma V^{T} S 0 = U Σ V T . Here, U U U and V V V are independently, uniformly sampled in SO ( 3 ) \operatorname{SO}(3) SO ( 3 ) , while the generation of Σ = diag ( s 1 , s 2 , s 3 ) \Sigma=\operatorname{diag}(s_{1},s_{2},s_{3}) Σ = diag ( s 1 , s 2 , s 3 ) depends on U U U and V V V . We sample ( s 1 , s 2 , s 3 ) (s_{1},s_{2},s_{3}) ( s 1 , s 2 , s 3 ) within the region w ( U Σ V T ) ≤ w max w(U\Sigma V^{T})\leq w_{\max} w ( U Σ V T ) ≤ w m a x according to the distribution
f ( s 1 , s 2 , s 3 ) ∝ ∣ s 1 2 − s 2 2 ∣ ∣ s 2 2 − s 3 2 ∣ ∣ s 1 2 − s 3 2 ∣ , (133) f(s_{1},s_{2},s_{3})\propto\left\lvert s_{1}^{2}-s_{2}^{2}\right\rvert\left\lvert s_{2}^{2}-s_{3}^{2}\right\rvert\left\lvert s_{1}^{2}-s_{3}^{2}\right\rvert, \tag*{(133)} f ( s 1 , s 2 , s 3 ) ∝ s 1 2 − s 2 2 s 2 2 − s 3 2 s 1 2 − s 3 2 , (133)
and then sort them to restore s 1 ≥ s 2 ≥ s 3 s_{1}\geq s_{2}\geq s_{3} s 1 ≥ s 2 ≥ s 3 . This procedure ensures that the projection of S 0 S_{0} S 0 on SO ( 3 ) \operatorname{SO}(3) SO ( 3 ) , i.e., U V T UV^{T} U V T , is uniformly distributed, while for each ( U , V ) (U,V) ( U , V ) , the conditional distribution of S 0 S_{0} S 0 follows the standard measure on R 3 × 3 \mathbb{R}^{3\times3} R 3 × 3 . The following algorithm analysis is based on this distribution, but one may well use other distributions to improve the performance of Algorithm 1.
We begin by considering the probability that a given IMT ( H A , H B , Q ) (H_{A},H_{B},Q) ( H A , H B , Q ) is generated in a single iteration. This can be estimated using the intersection between the cyan region and the pink hypercube centered at Q Q Q in Figure 7 .
Figure 7. A schematic diagram showing how Algorithm 1 works, where 9D regions are drawn as 2D shapes for intuitive understanding. (a) Ω S 0 \Omega_{S_0} Ω S 0 (cyan) is a neighborhood of S O ( 3 ) \mathrm{SO}(3) SO ( 3 ) determined solely by Y i j k l A Y^{A}_{ijkl} Y ij k l A , Y i j k l B Y^{B}_{ijkl} Y ij k l B and w max w_{\max} w m a x . The trial matrices { S 0 } \{S_0\} { S 0 } (blue diamonds) are generated in Ω S 0 \Omega_{S_0} Ω S 0 , approximating the exact deformation gradients (red stars). (b) ϕ H A , H B \phi_{H_A,H_B} ϕ H A , H B is applied to { S 0 } \{S_0\} { S 0 } , and then each ϕ H A , H B ( S 0 ) \phi_{H_A,H_B}(S_0) ϕ H A , H B ( S 0 ) is rounded to the nearest integer matrix (gray dots). Each element of { Q } \{Q\} { Q } (red stars in cyan region) is produced if and only if a S 0 S_0 S 0 lies within its “preimage of rounding” (pink squares). Currently, the algorithm should continue to generate a denser { S 0 } \{S_0\} { S 0 } to produce the topmost Q Q Q in the figure.
Given that strains in SSPTs are usually small, the intersection can be considered as a thin vicinity of the 3D section of Eq. (87) intercepted by SO(3). Therefore, the probability of ( H A , H B , Q ) (H_A, H_B, Q) ( H A , H B , Q ) being generated is approximately equal to the probability that ϕ H A , H B ( U V T ) \phi_{H_A,H_B}(UV^T) ϕ H A , H B ( U V T ) is generated within this section. Since the cyan region contains Q Q Q , the volume of this section can be assumed to be no less than 1. On the other hand, U V T UV^T U V T is uniformly distributed over SO(3), whose volume as a 3D submanifold is 16 2 π 2 16\sqrt{2}\pi^2 16 2 π 2 . Hence, after the deformation by ϕ H A , H B \phi_{H_A,H_B} ϕ H A , H B , the probability density near Q Q Q is at least
η H A , H B = σ 7 ( ϕ H A , H B ) σ 8 ( ϕ H A , H B ) σ 9 ( ϕ H A , H B ) 16 2 π 2 (134) \eta_{H_A,H_B}=\frac{\sigma_7(\phi_{H_A,H_B})\sigma_8(\phi_{H_A,H_B})\sigma_9(\phi_{H_A,H_B})}{16\sqrt{2}\pi^2} \tag*{(134)} η H A , H B = 16 2 π 2 σ 7 ( ϕ H A , H B ) σ 8 ( ϕ H A , H B ) σ 9 ( ϕ H A , H B ) (134)
where
ϕ H A , H B = ( H B − 1 C B − 1 ) ⊗ ( H A T C A T ) (135) \phi_{H_A,H_B}=(H_B^{-1}C_B^{-1})\otimes(H_A^T C_A^T) \tag*{(135)} ϕ H A , H B = ( H B − 1 C B − 1 ) ⊗ ( H A T C A T ) (135)
is treated as a 9 × 9 9 \times9 9 × 9 matrix.
Now we consider the probability that no IMT in a given congruence class is generated in a single iteration. Since each IMT corresponds to an SLM, ( H A ′ , H B ′ , Q ′ ) (H'_A,H'_B,Q') ( H A ′ , H B ′ , Q ′ ) is congruent to ( H A , H B , Q ) (H_A,H_B,Q) ( H A , H B , Q ) if and only if there exist R A ∈ G A ′ R_A \in G'_A R A ∈ G A ′ and R B ∈ G B ′ R_B \in G'_B R B ∈ G B ′ such that
H A ′ = hnf ( R ^ A H A ) , (136) H'_A=\operatorname{hnf}(\hat{R}_A H_A), \tag*{(136)} H A ′ = hnf ( R ^ A H A ) , (136)
H B ′ = hnf ( R ^ B H B ) , (137) H'_B=\operatorname{hnf}(\hat{R}_B H_B), \tag*{(137)} H B ′ = hnf ( R ^ B H B ) , (137)
H B ′ Q ′ H A ′ − 1 = H B Q H A − 1 , (138) H'_B Q' H_A'^{-1}=H_B Q H_A^{-1}, \tag*{(138)} H B ′ Q ′ H A ′ − 1 = H B Q H A − 1 , (138)
where R ^ A = C A − 1 R A C A \hat{R}_A=C_A^{-1}R_A C_A R ^ A = C A − 1 R A C A and R ^ B = C B − 1 R B C B \hat{R}_B=C_B^{-1}R_B C_B R ^ B = C B − 1 R B C B are unimodular matrices that describe how R A R_A R A and R B R_B R B change the base matrices of L A L_A L A and L B L_B L B , respectively. Therefore, the probability that no IMT congruent to ( H A , H B , Q ) (H_A,H_B,Q) ( H A , H B , Q ) is generated has a lower bound
ζ H A , H B = ∏ R A ∈ G A ′ ∏ R B ∈ G B ′ ( 1 − η H A ′ , H B ′ ) . (139) \zeta_{H_A,H_B}=\prod_{R_A\in G'_A}\prod_{R_B\in G'_B}(1-\eta_{H'_A,H'_B}). \tag*{(139)} ζ H A , H B = R A ∈ G A ′ ∏ R B ∈ G B ′ ∏ ( 1 − η H A ′ , H B ′ ) . (139)
Replacing ( 1 − η ) (1-\eta) ( 1 − η ) in Eq. (89) with this expression yields a significantly smaller
i t h = ln ϵ ln max H A , H B ζ H A , H B , (140) i_{\mathrm{th}}=\frac{\ln\epsilon}{\ln\max_{H_A,H_B}\zeta_{H_A,H_B}}, \tag*{(140)} i th = ln max H A , H B ζ H A , H B ln ϵ , (140)
which can be computed numerically before Algorithm 1 starts.
References