IRA library documentation

GitHub repository Online documentation and tutorials

Reference

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

Compilation

Traditional make

To compile the IRA library, you need the lapack library. On a standard linux machine, it should suffice to type:

cd src/
make all

This will generate the static and shared libraries: libira.a, and libira.so. To compile only one of them, type make lib or make shlib, respectively.

To clean the build type:

make clean

lapack library

The lapack library is needed for compilation. Default flag is LIBLAPACK=-llapack, however if you wish to change that, i.e. with openblas, you can specify it from the command as:

LIBLAPACK=-lopenblas make all

If the lapack library is not available on your system, you can leave the variable undefined (this will compile a local version of the needed lapack routines, which is however not optimal):

LIBLAPACK='' make all

conda compatible build

For local machines, it is possible to use pixi [pixi-install] to get a working version of the Python bindings in a fairly automated manner.

curl -fsSL https://pixi.sh/install.sh | bash
# build the library with openblas
pixi run build_lib
pixi shell # sets the environment variable
cd examples/IRA
python python_program.py
pixi-install

Installation instructions here: https://pixi.sh/latest/

Linking a program to libira

A program compiled with gcc or gfortran can easily link the IRA library, as-is, by linking either the shared library libira.so, or the static version libira.a. They are both located in the src/ directory after compilation.

Example for fortran program:

gfortran -o caller_program.x caller_program.f90 -L/your/path/to/IRA/src/ -lira -Wl,-rpath,/your/path/to/IRA/src

The base-level implementations are not placed in modules, therefore all routines are in principle acessible to the caller. Care must be taken to ensure the correct type, kind, shape, etc. of the arguments, i.e. interface matching needs to be checked manually. The default precision is equivalent to c_int for integers, and c_double for reals.

The C-headers are located in the IRA/interface directory, and can be included in compilation by -I/your/path/to/IRA/interface.

When linking the static library libira.a to a C-program, you need to add the math (-lm), and fortran (-lgfortran, or equivalent) to the compilation:

gcc -I/your/path/IRA/interface -o c_prog.x c_prog.c -L/your/path/to/IRA/src -lira -Wl,-rpath,/your/path/to/IRA/src -lm -lgfortran

Tutorials and How-to

(under construction)