Introduction

Even though this library is called the IRA library, there are three main algorithms contained inside:

  • CShDA: Constrained Shortest Distance Assignments;

  • IRA: Iterative Rotations and Assignments;

  • SOFI: Symmetry Operation FInder.

Each of those algorithms is designed to solve a different problem related to characterization of generic atomic structures.

Some other miscallaneous routines are contained, see the section of How-to guides.

CShDA

Constrained Shortest Distance Assignments (CShDA, [ira2021]) is the really fundamental algorithm for the rest of this library. It solves the so-called Linear Assignment Problem (LAP), and then computes the distance between two atomic structures \(A\) and \(B\).

More precisely, it solves the problem sometimes referred to as bottleneck-LAP, and uses that solution to compute the Hausdorff distance:

\[d_H( A, B ) = \max_i \min_j \big\{ d(a_i, b_j) \big\} \qquad(1)\]

where \(a_i \in A\) and \(b_j \in B\) are atomic positions, and \(d()\) is the Cartesian distance function.

By first solving the LAP, computing the distance between two atomic structures becomes trivial. In fact, such distance is invariant to permutations of atoms \(P_B\), and variant to all other rigid transformations. CShDA returns the atomic permutations, and values of atom-atom distances w.r.t. the permutation: distances \(d(a_i, b_i)\), with indices \(i\), after applying the permutation computed in the beginning (LAP solution). Finally, the distance between \(A\) and \(B\) is taken as the maximal value in the set.

It enforces a strict one-to-one assignment of the atoms, and works also for structures containing different numbers of atoms.

Since CShDA is quite computationally heavy, a heuristic early-exit criterion is set up, and used whenever possible. The criterion is in the form of a distance threshold: as soon as it is established that the final distance value returned by CShDA cannot be below the given threshold, the computation exits with a high distance value. The heuristic can be disregarded by simply inputting a very high value for this threshold.

(under construction)

IRA

Iterative Rotations and Assignments (IRA, [ira2021]) solves the so-called shape matching problem, also sometimes called structural alignment, or similar:

\[P_B B = \mathbf{R} A + \mathbf{t} \qquad (2)\]

where \(A\) and \(B\) are two atomic structures, \(\mathbf{R}\) is a rotation/reflection matrix, \(\mathbf{t}\) is a translation vector, and \(P_B\) is a permutation matrix of atomic indices in \(B\).

The problem of finding an optimal rotation \(\mathbf{R}\) when \(A\) and \(B\) do not include permutations is known as the orthogonal Procrustes problem, and can be easily solved by Singular Value Decomposition method (SVD), see the wikipedia article. The routines to solve it are also included in this library.

The shape-matching problem of Eq. (2) is however more complicated, and can be rewritten as optimization problem:

\[\DeclareMathOperator*{\argmin}{arg\,min} \argmin_{\bf R,t} \big\{ D({\bf R}A + {\bf t}, B) \big\} \qquad (3)\]

in which \(D\) is a general distance function between two sets, that is (i) variant under \({\bf R}\) and \({\bf t}\), (ii) invariant under permutation \(P_B\), and (iii) returns value 0 when \({\bf R}\) and \({\bf t}\) are such that Eq. (2) is satisfied, i.e. when the best match is found.

The function \(D\) in Eq. (3) is computed by CShDA.

The IRA algorithm specifies a way to parse the space of rigid transformations associated to the atomic structure, computes CShDA on the way, and returns the single transformation that minimizes it. In presence of distortions, it calls the SVD-based algorithm to further minimize the rotations, given permutation computed by CShDA.

When \(A\) and \(B\) are congruent, IRA is guaranteed to return the optimal solution, independently of the initial orientation and permutation of the structures, which is not entirely obvious (see benchmarks in [ira2021]). In case of nearly-congruent structures, this becomes debatable, since the notion of near-congruency is not uniquely defined, and is dependent on the involved structures.

Therefore, IRA is not recommended for applications where the value of (dis-)similarity between structures is the key quantity. It is however highly efficient in tasks like retrieving a certain structure from a list of structures, where the structure is certain to be present in the list (in any orientation and permutation).

ira2021(1,2,3)

  1. Gunde, N. Salles, A. Hemeryck, L. Martin-Samos, JCIM, 2021, DOI: 10.1021/acs.jcim.1c00567, arXiv: 2111.00939

SOFI

Symmetry Operation Finder (SOFI, [sofi2024]) is an algorithm for finding point group symmetry operations of atomic structures.

By definition, the transformation of a structure by a symmetry operation, should give a structure that is equivalent to the original, up to a permutation of indices:

\[P_A A = \boldsymbol{\theta} A \qquad (4)\]

where \(A\) is an atomic structure, \(P_A\) is a permutation of atomic indices in \(A\), and \(\boldsymbol{\theta}\) is a symmetry operation in the form of 3x3 orthonormal matrix.

Notice the similarity of Eq. (4) to Eq. (2): the structure \(B\) is now equal to \(A\), the rigid transformation \(\mathbf{R}\) becomes a symmetry operation \(\boldsymbol{\theta}\), and the translation \(\mathbf{t}\) vanishes.

When the structure \(A\) contains point group symmetries, Eq. (4) has degenrate solutions in form of pairs \((\boldsymbol{\theta}, P_A)\). The set of all such pairs represents the set of point group symmetry operations for the structure. SOFI solves this problem. It can be seen as an extension of IRA, where IRA gives a single, optimal solution to matching two (near-)congruent structures, SOFI gives all degenerate solutions of matching a structure to itself.

sofi2024

  1. Gunde, N. Salles, L. Grisanti, L. Martin-Samos, A. Hemeryck, JCP, 2024, DOI: 10.1063/5.0215689, arXiv: 2408.06131